利用栈实现逆波兰表达式求值
发布网友
发布时间：2022-04-22 13:32
共3个回答
热心网友
时间：2022-05-11 05:52
#include <stdio.h>
#include <ctype.h>//判断是否为字符的函数的头文件
#define maxsize 100
typedef int elemtype;
typedef struct sqstack sqstack;//由于sqstack不是一个类型 而struct sqstack才是
char ch[7]={'+','-','*','/','(',')','#'};//把符号转换成一个字符数组
int f1[7]={3,3,5,5,1,6,0};//栈内元素优先级
int f2[7]={2,2,4,4,6,1,0};//栈外的元素优先级
struct sqstack
{
elemtype stack[maxsize];
int top;
};
void Initstack(sqstack *s)
{
s->top=0;
}
void Push(sqstack *s,elemtype x)
{
if(s->top==maxsize-1)
printf("Overflow\n");
else
{
s->top++;
s->stack[s->top]=x;
}
}
void Pop(sqstack *s,elemtype *x)
{
if(s->top==0)
printf("underflow\n");
else
{
*x=s->stack[s->top];
s->top--;
}
}
elemtype Gettop(sqstack s)
{
if(s.top==0)
{
printf("underflow\n");
return 0;
}
else
return s.stack[s.top];
}
elemtype f(char c)
{
switch(c)
{
case '+':
return 0;
case '-':
return 1;
case '*':
return 2;
case '/':
return 3;
case '(':
return 4;
case ')':
return 5;
default:
return 6;
}
}
char precede(char c1,char c2)
{
int i1=f(c1);
int i2=f(c2);//把字符变成数字
if(f1[i1]>f2[i2])//通过原来设定找到优先级
return '>';
else if(f1[i1]<f2[i2])
return '<';
else
return '=';
}
int Operate(elemtype a,elemtype theta,elemtype b)
{
int sum;
switch(theta)
{
case 0:
sum=a+b;
break;
case 1:
sum=a-b;
break;
case 2:
sum=a*b;
break;
default:
sum=a/b;
}
return sum;
}
EvaluateExpression()
{
char c;
int i=0,sum=0;
int k=1,j=1;//设置了开关变量
elemtype x,theta,a,b;
sqstack OPTR,OPND;
Initstack(&OPTR);
Push(&OPTR,f('#'));//0压入栈
Initstack(&OPND);
c=getchar();
if(c==ch[2]||c==ch[3]||c==ch[5]||c==ch[6])//先对＋和-的情况忽略和左括号的情况
{
printf("错误1 \n");
k=0;
return 0;
}
if(c==ch[0])
c=getchar();//如果是＋，把它覆盖
if(c==ch[1])
{
j=0;
c=getchar();//也把－号覆盖
}
while(c!='#'||ch[Gettop(OPTR)]!='#')
{
if(isdigit(c))
{
sum=0;
while(isdigit(c))
{
if(!j)
{
sum=sum*10-(c-'0');//实现了数字串前面有负号（之前是：sum=-(sum*10)-(c-'0')结果是－12＋13＝21）
}
else
sum=sum*10+(c-'0');
c=getchar();
}
Push(&OPND,sum);//如果还是数字先不压栈，把数字串转化成十进制数字再压栈
j=1;
}
else
if(k)
{
switch(precede(ch[Gettop(OPTR)],c))
{
case'<': Push(&OPTR,f(c));//把它们整型化
c=getchar();
if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c=='\n')//要除去下个是‘（’的情况 也把以运算符归到这里来
{
printf("出错2\n");
k=0;
return 0;//加了开关变量和返回0的值使程序更以操作
}
break;
case'=': Pop(&OPTR,&x);
c=getchar();
if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c=='\n')//把ch[6]的情况也忽略了但此时并没有注意到右括号后面右运算符的情况
{
printf("出错2\n");
k=0;
return 0;
}
break;
case'>': Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);//注意这里是谁先出栈
Push(&OPND,Operate(a,theta,b));
break;
}
}
}//在这里判断是否以运算符结束是不对的
return(Gettop(OPND));
}
main()
{
int result;
printf("输入你的算术表达式：\n");
result=EvaluateExpression();
printf("结果是 :%d\n",result);
return 0;
}
【jixingzhong】:
本计算器利用堆栈来实现。
1、定义后缀式计算器的堆栈结构
因为需要存储的单元不多，这里使用顺序栈，即用一维数组来模拟堆栈：
#define MAX 100
int stack[MAX];
int top=0;
因此程序中定义了长度为MAX的一维数组，这里MAX用宏定义为常数100，我们可以修改宏定义而重新定义堆栈的大小。
整型数据top为栈顶指示，由于程序开始时堆栈中并无任何数据元素，因此top被初始化为0。
2、存储后缀式计算器的运算数
我们定义了堆栈stack[MAX]后，就可以利用入栈操作存储先后输入的两个运算数。
下面看一下是如何实现的：
int push(int i) /*存储运算数，入栈操作*/
{
if(top<MAX)
{
stack[++top]=i; /*堆栈仍有空间，栈顶指示上移一个位置*/
return 0;
}
else /*堆栈已满，给出错误信息，返回出错指示*/
{
printf("The stack is full");
return ERR;
}
}
我们在调用函数push时，如果它的返回值为0，说明入栈操作成功；否则，若返回值为ERR(在程序中说明为-1)，说明入栈操作失败。
3、从堆栈中取出运算数
当程序中读完了四则运算符后，我们就可以从堆栈中取出已经存入的两个运算数，构成表达式，计算出结果。取出运算数的函数采用的正是出栈算法。在本例中，实现该算法的函数 为pop():
int pop(); /*取出运算数，出栈操作*/
{
int var; /*定义待返回的栈顶元素*/
if(top!=NULL) /*堆栈中仍有数据元素*/
{
var=stack[top--]; /*堆栈指示下移一个位置*/
return var;
}
else /*堆栈为空，给出错误信息，并返回出错返回值*/
printf("The stack is cmpty!\n");
return ERR;
}
同样，如果堆栈不为空，pop()函数返回堆栈顶端的数据元素，否则，给出栈空提示，并返回错误返回值ERR。
4、设计完整的后缀式计算器
有了堆栈存储运算数，后缀式计算器的设计就很简单了。程序首先提示用户输入第一个运算数，调用push()函数存入堆栈中；而后提示用户输入第二个运算数，同样调用push()函数存入堆栈中。接下来，程序提示用户输入+,-,*,/四种运算符的一种，程序通过switch_case结构判断输入运算符的种类，转而执行不同的处理代码。以除法为例，说明程序的执行流程：
case '/':
b=pop();
a=pop();
c=a/b;
printf("\n\nThe result is %d\n",c);
printf("\n");
break;
程序判断用户输入的是除号后，就执行上述代码。首先接连两次调用pop()函数从堆栈中读出先前输入的运算数，存入整型数a和b中；然后执行除法运算，结果存入单元c中。这时需要考虑究竟谁是被除数，谁是除数。由于开始我们先将被除数入栈，根据堆栈“先进后出”的原则，被除数应该是第二次调用pop()函数得到的返回值。而除数则是第一次调用pop()函数得到的返回值。
最后程序打印出运算结果，并示提示用户是否继续运行程序：
printf("\t Continue?(y/n):");
l=getche();
if(l=='n')
exit(0);
如果用户回答是"n"，那么结束程序，否则继续循环。
完整的程序代码如下：
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define ERR -1
#define MAX 100 /*定义堆栈的大小*/
int stack[MAX]; /*用一维数组定义堆栈*/
int top=0; /*定义堆栈指示*/
int push(int i) /*存储运算数,入栈操作*/
{
if(top<MAX)
{
stack[++top]=i; /*堆栈仍有空间，栈顶指示上移一个位置*/
return 0;
}
else
{
printf("The stack is full");
return ERR;
}
}
int pop() /*取出运算数，出栈操作*/
{
int var; /*定义待返回的栈顶元素*/
if(top!=NULL) /*堆栈中仍有元素*/
{
var=stack[top--]; /*堆栈指示下移一个位置*/
return var; /*返回栈顶元素*/
}
else
printf("The stack is empty!\n");
return ERR;
}
void main()
{
int m,n;
char l;
int a,b,c;
int k;
do{
printf("\tAriothmatic Operate simulator\n"); /*给出提示信息*/
printf("\n\tPlease input first number:"); /*输入第一个运算数*/
scanf("%d",&m);
push(m); /*第一个运算数入栈*/
printf("\n\tPlease input second number:"); /*输入第二个运算数*/
scanf("%d",&n);
push(n); /*第二个运算数入栈*/
printf("\n\tChoose operator(+/-/*//):");
l=getche(); /*输入运算符*/
switch(l) /*判断运算符，转而执行相应代码*/
{
case '+':
b=pop();
a=pop();
c=a+b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
case '-':
b=pop();
a=pop();
c=a-b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
case '*':
b=pop();
a=pop();
c=a*b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
case '/':
b=pop();
a=pop();
c=a/b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
}
printf("\tContinue?(y/n):"); /*提示用户是否结束程序*/
l=getche();
if(l=='n')
exit(0);
}while(1);
}
【studyall123】:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define STACK_INIT_SIZE 100 //初始分配量
#define STACKINCREMENT 10 //存储空间的分配增量
typedef char ElemType;
typedef ElemType OperandType; //操作数
typedef char OperatorType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{
//构造一个空栈S
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack S){
ElemType e;
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return e;
}
Status Push (SqStack &S,ElemType e)
{
//插入元素e为新的栈顶元素
if (S.top - S.base >= S.stacksize){
S.base = (ElemType *) realloc ( S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop (SqStack &S,ElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top == S.base) return ERROR;
e = * --S.top;
return OK;
}
char In(char c,char OP[])
{
if(c>=35 && c<=47)
return 1;
else return 0;
}
char OP[8]={'+','-','*','/','(',')','#','\0'};
int m[7][7]={1,1,2,2,2,1,1,
1,1,2,2,2,1,1,
1,1,1,1,2,1,1,
1,1,1,1,2,1,1,
2,2,2,2,2,0,-1,
1,1,1,1,-1,1,1,
2,2,2,2,2,-1,0};//1 > 2 < 0 = -1 不存在
char Precede(char i,char j)
{
int a,b; char *p;
for(p=OP,a=0;*p!='\0';p++,a++)
if(*p==i) break;
for(p=OP,b=0;*p!='\0';p++,b++)
if(*p==j) break;
if(m[a][b]==1) return '>';
else if(m[a][b]==2) return '<';
else if(m[a][b]==0) return '=';
else return 'O';
}
char Operate(char a,char theta,char b)
{
if(a>47) a=atoi(&a);
if(b>47) b=atoi(&b);
switch(theta)
{
case '+': return a+b;
break;
case '-': return a-b;
break;
case '*': return a*b;
break;
case '/': return a/b;
break;
}
}
OperandType EvaluateExpression()
{
SqStack OPTR,OPND;
OperandType a,b,c; OperatorType theta;
InitStack(OPTR); Push(OPTR,'#');
InitStack(OPND); c=getchar();
while (c!='#' || GetTop(OPTR)!='#')
{
if (!In(c,OP)){Push(OPND,c);c=getchar();}
else
switch(Precede(GetTop(OPTR),c))
{
case '<' :
Push(OPTR,c); c = getchar();
break;
case '=' :
Pop(OPTR,c); c = getchar();
break;
case '>' :
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}
}
return GetTop(OPND);
}
void main()
{
printf("(以#为结束符)\n");
printf("请输入：\n");
int a;
a=(int)EvaluateExpression();
printf("%d",a);
getch();
}
【laiwusheng】:
ls都正确
【Jim_King_2000】:
C++ In Action这本书里面有表达式求值的详细项目分析.
【xlbdan】:
数据结构的书里面都有的,仔细看一下
【zpk1234】:
studyall123的只能对0到9的数字运算才有效,对于10以上的数字就不行!不知道有没有更好的方法!
【sjjf】:
现在的人，连google一下都懒啊
【aaron85】:
实际上是按照逆波兰式的顺序让输入的表达式入栈，再根据运算符优先级来计算。
【pomiox】:
lenrning!
热心网友
时间：2022-05-11 07:10
二．软件需求：数据对象：D={ ai |ai∈ElemSet,i=1,2,3,……，n，n≥0}
数据关系：R={<ai-1,ai,)>| ai-1,ai ∈D, i=2,3,……，n}约定a1为栈底，an 为栈顶。基本操作：Push(&s,e)
初始条件：栈s已经存在。
操作结果：插入元素e为新的栈顶元素
Pop(&s,&e)
初始条件：栈s已经存在且非空。
操作结果：删除s的栈顶元素，并用e返回其值
3 系统设计：
流程图：
二、实验内容及要求
当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实数范围内。对于异常表达式给出错误提示。
三、实验设备及软件。
PC机、VC++6.0
四、设计方案。
一 题目（老师给定或学生自定）：迷宫求解问题
二 设计的主要思路：
l 表达式用单链表储存，你可以看到这个链表中既有操作数又有操作符，如果你看过我的《如何在一个链表中链入不同类型的对象》，这里的方法也是对那篇文章的补充。
l 输入表达式时，会将原来的内容清空，并且必须按照中缀表示输入。如果你细看一下中缀表达式，你就会发现，除了括号，表达式的结构是“操作数”、“操作符”、“操作数”、……“操作符（＝）”，为了统一这个规律，同时也为了使输入函数简单一点，规定括号必须这样输入“0（”、“）0”；这样一来，“0”就不能作为操作数出现在表达式中了。因为我没有在输入函数中增加容错的语句，所以一旦输错了，那程序就“死”了。
l 表达式求值的过程是，先变成后缀表示，然后用后缀表示求值。因为原书讲解的是这两个算法，并且用这两个算法就能完成中缀表达式的求值，所以我就没写中缀表达式的直接求值算法。具体算法说明参见原书，我就不废话了。
l Calculate()注释掉的两行，“％”是因为只对整型表达式合法，“^”的Power()函数没有完成。
l isp()，icp()的返回值，原书说的不细，我来多说两句。‘＝’（表达式开始和结束标志）的栈内栈外优先级都是最低。‘（’栈外最高，栈内次最低。‘）’栈外次最低，不进栈。‘^’栈内次最高，栈外比栈内低。‘×÷％’栈内比‘^’栈外低，栈外比栈内低。‘＋－’栈内比‘×’栈外低，栈外比栈内低。这样，综合起来，就有9个优先级，于是就得出了书上的那个表。(CSDN)
三 主要功能：
《1》生成迷宫地图
《2》寻找出口路径
《3》随机生成迷宫地图
《4》取得当前通道块当前方向上的下一个通道块
《5》显示迷宫地图
说明：此五个函数模块主要为最后生成一个动态的迷宫作准备。
五、主要代码及分析
//-------------------栈数据结构的声明----------------------------
#include<iostream.h>
#include<fstream.h>
#include <string.h>
#include<iomanip.h>
#include<assert.h>
#include <ctype.h>
#include <conio.h>
#include <stdlib.h>
#include <strstrea.h>
const int SM = 100;
template <class Type> //顺序栈的类定义
class Stack
{
public:
Stack(int=100);//构造函数，初始化栈
~Stack()//析构函数，删除栈中的动态空间
{
delete [] elements;
}
void Push(const Type &item);//向栈中插入元素
Type GetTop();//读取栈顶元素
Type Pop();//从栈中删除元素
void MakeEmpty()//清空栈
{ top=-1;}
int IsEmpty()const//判断栈是否为空
{
return top==-1;
}
int IsFull()const//判断是否已满
{
return top==MaxSize-1;
}
private:
Type *elements;//存放栈中元素的栈数组
int top;//栈顶指针
int MaxSize;//栈的最大可容纳元素个数
};
//---------------栈成员函数的实现---------------
template<class Type>Stack<Type>::Stack(int s):top(-1),MaxSize(s)
{//建立一个最大尺寸为s的空栈，若分配不成功则错误处理。
elements=new Type[MaxSize]; //创建栈空间
assert(elements!=0); //断言：动态存储成功分配与否
}
template<class Type>void Stack<Type>::Push(const Type &item)
{//若栈不满，则将元素item插入到该栈的的栈顶，否则出错处理
assert(!IsFull());
elements[++top] = item;
}
template<class Type>Type Stack<Type>::Pop()
{//如果栈不空则函数返回该栈顶元素的值然后栈顶指针退1
assert(!IsEmpty()); // 断言：判断栈空否，若断言成立则继续执行
return elements[top--]; //返回栈顶元素的值
}
template<class Type>Type Stack<Type>::GetTop()
{//若栈不空则返回该栈顶元素的值
assert(!IsEmpty()); //断言：判断栈空否，若断言成立则继续执行
return elements[top]; //返回栈顶元素的值
}
//----------------------------工具函数的定义------------------------------
//求运算符优先级
int Youxianji(char op)
{
switch (op)
{
case '+':
case '-':
return 1;//定义加减运算的优先级为1
case '*':
case '/':
return 2;//定义乘除运算的优先级为2
case '(':
case '[':
case '{':
case '=':
default:
return 0;//定义在栈中的左括号和栈底字符的优先级为0
}
}
//将中缀表达式转换成后缀表达式
void Change(char *s1,char *s2)
{
Stack<char> R(SM);//定义用于暂存运算符的栈
R.Push('=');//给栈底放入‘='字符，它具有最低优先级0
int i,j;
i = 0;//用于指示扫描s1串中字符的位置，初值为0
j = 0;//用于指示s2串中待存字符的位置，初值为0
char ch = s1[i];
while (ch != '=')
{
if (ch == ' ')
{
ch = s1[++i];//对于空格字符不做任何处理
}
//-------------------------------------------------------------
else if (ch == '(')
{//对于左括号，直接进栈
R.Push(ch);
ch = s1[++i];
}
else if (ch == ')')
{//对于右括号，使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while (R.GetTop() != '(')
{
s2[j++] = R.Pop();
}
R.Pop();//删除栈顶的左括号
ch = s1[++i];
}
//-------------------------------------------------
else if (ch == '[')
{//对于左括号，直接进栈
R.Push(ch);
ch = s1[++i];
}
else if (ch == ']')
{//对于右括号，使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while (R.GetTop() != '[')
{
s2[j++] = R.Pop();
}
R.Pop();//删除栈顶的左括号
ch = s1[++i];
}
//---------------------------------------------
else if (ch == '{')
{//对于左括号，直接进栈
R.Push(ch);
ch = s1[++i];
}
else if (ch == '}')
{//对于右括号，使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while (R.GetTop() != '{')
{
s2[j++] = R.Pop();
}
R.Pop();//删除栈顶的左括号
ch = s1[++i];
}
//---------------------------------------------------
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{//对于四则运算符，使暂存在栈中的不低于ch优先级
//的运算符依次出栈并写入到s2中
char w = R.GetTop();
while (Youxianji(w) >= Youxianji(ch))
{//Youxianji()函数返回运算符形参的优先级
s2[j++] = w;
R.Pop();
w = R.GetTop();
}
R.Push(ch);
ch = s1[++i];
}
else
{//此处为数字或小数点字符的处理
while (isdigit(ch) || ch == '.')
{
s2[j++] = ch;
ch = s1[++i];
}
s2[j++] = ' ';//被转换后的每个数值后放一个空格
}
}
//---------------------------------------------------------
ch = R.Pop();
while (ch != '=')
{
if (ch == '('||ch == '{'||ch == '[')
{
cout<<"表达式错误!"<<endl;
exit(1);
}
else
{
s2[j++] = ch;
ch = R.Pop();
}
}
s2[j++] = '=';//加入字符串结束符
s2[j++] = '\0';
}
//计算后缀表达式值
float Compute(char *s2)
{
Stack<float> S(SM);//用S栈存储操作数和中间计算结果
istrstream ins(s2);//把s2定义为输入字符串流对象ins
char ch;//用于输入字符
float x;//用于输入浮点数
ins>>ch;
while (ch != '=')
{
switch (ch)
{
case '+':
x = S.Pop() + S.Pop();
break;
case '-':
x = S.Pop();
x = S.Pop() - x;
break;
case '*':
x = S.Pop() * S.Pop();
break;
case '/':
x = S.Pop();
if (x != 0.0)//判断除数是否为零
{
x = S.Pop() / x;
}
else
{
cout<<"除数不能为零!"<<endl;
exit(1);
}
break;
default:
ins.putback(ch);
ins>>x;
}
S.Push(x);
ins>>ch;
}
if (!S.IsEmpty())
{
x = S.Pop();
if (S.IsEmpty())//如果栈中只有一个值那一定是结果
{
return x;
}
else
{
cout<<"表达式错误!"<<endl;
exit(1);
}
}
else
{
cout<<"表达式错误!"<<endl;
exit(1);
}
}
//判断是否为运算符
int IsYf(char ch)
{
switch (ch)
{
case '+':
case '-':
case '*':
case '/':
return 1;
break;
default:
return 0;
break;
}
}
//提示信息显示
void Tishi(int n)
{
switch (n)
{
case 0:
cout<<"..."<<endl;
break;
case 1:
cout<<"\n表达式首字符不能是运算符...请重新输入"<<endl;
break;
case 2:
cout<<"\n表达式中的运算符输入有误...请重新输入"<<endl;
break;
case 3:
cout<<"\n表达式中有非法字符...请重新输入"<<endl;
break;
case 4:
cout<<"\n没有以'='字符结束...请重新输入"<<endl;
break;
case 5:
cout<<"\n表达式括号不配对...请重新输入"<<endl;
break;
default:
break;
}
}
//检查表达式是否有错
int Test(char *s1)
{
char ch;
int i=0;
int left1 = 0;//统计左括号
int right1 = 0;//统计右括号
int left2 = 0;//统计左括号
int right2 = 0;//统计右括号
int left3 = 0;//统计左括号
int right3 = 0;//统计右括号
ch = s1[i++];
if (ch =='\0')//没有输入了表达式
{
Tishi(0);
return 0;
}
if (IsYf(ch))//第一个是运算符
{
Tishi(1);
return 0;
}
while (ch != '\0')
{
if (IsYf(ch) && IsYf(s1[i]))//运算符错误
{
Tishi(2);
return 0;
}
if ((ch < '0') || (ch > '9'))//有否非法字符
{
switch (ch)
{
case '('://合法字符
left1++;
break;
case ')':
right1++;
break;
case '['://合法字符
left2++;
break;
case ']':
right2++;
break;
case '{'://合法字符
left3++;
break;
case '}':
right3++;
break;
case ' ':
case '+':
case '-':
case '*':
case '/':
case '=':
case '.':
break;
default://非法字符
Tishi(3);
return 0;
break;
}
}
ch = s1[i++];
}
if (s1[i-2] != '=')//结束符错误
{
Tishi(4);
return 0;
}
if (left1!=right1||left2!=right2||left3!=right3)//括号问题
{
Tishi(5);
return 0;
}
return 1;//表达式正确
}
//-----------------------------END--------------------------
//-----------------------------主函数------------------
void main()//主程序
{
char str1[50],str2[50]; //暂时存储表达式
int i;
cout<<" =================欢迎使用！=================="<<endl;
cout<<endl;
while(i!=0)
{
cout<<" 请输入一个以'='字符结束的中缀算术表达式："<<endl;
cin.getline(str1,sizeof(str1));
while(!Test(str1)) //检查表达式是否正确
{
cin.getline(str1,sizeof(str1));
}
Change(str1,str2); //处理结果
cout<<"\n求值结果为： "<<str1<<Compute(str2)<<endl;
cout<<endl;
cout<<"如果继续请输入 ：1"<<endl;
cin>>i;
}
}
//-----------------------------END-----------------------------
六．测试结果及说明
=================欢迎使用！==================
请输入一个以'='字符结束的中缀算术表达式：
{(0-3+4+9)*(0-3)*7/[(0-5)*2]-7}*2=
求值结果为： {(0-3+4+9)*(0-3)*7/[(0-5)*2]-7}*2=
如果继续请输入 ：1
3.5+12.3*15+8-(3/2+1)+2*2+3.2*3-5/6-3=
请输入一个以'='字符结束的中缀算术表达式：
求值结果为： .5+12.3*15+8-(3/2+1)+2*2+3.2*3-5/6
如果继续请输入 ：1
1
请输入一个以'='字符结束的中缀算术表达式：
...
2-2+5/7-[3+(1+2+3-9)*(4+5+6+7)]/9+8=
求值结果为： 2-2+5/7-[3+(1+2+3-9)*(4+5+6+7)]/9+
如果继续请输入 ：1
1
请输入一个以'='字符结束的中缀算术表达式：
...
(23-12.33)/{1.2+[(23-12.3)*(13-5)-6]/2}=
求值结果为： (23-12.33)/{1.2+[(23-12.3)*(13-5)-
如果继续请输入 ：1
1
请输入一个以'='字符结束的中缀算术表达式：
...
1/2/3/4/5/6/7/8/9=
求值结果为： 1/2/3/4/5/6/7/8/9=2.75573e-006
如果继续请输入 ：1
3,3*5+[12-(22-3*5)]+11*3.4=
请输入一个以'='字符结束的中缀算术表达式：
表达式中有非法字符...请重新输入
3.3*5+[12-(22-3*5)]+11*3.4=
求值结果为： 3.3*5+[12-(22-3*5)]+11*3.4=58.9
如果继续请输入 ：1
七、实验总结与心得体会
实验总结：
该程序虽然能运行出预计的结果但是还存在一些问题
1．由于对栈的算法的推敲不足，使程序调试时有些费时
2．本程序有些代码不够完善，有待进一步改进。
心得体会：
6 总结：
表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的一个典型例子。这里用静态栈实现表达式求值，包含了加，减，乘，除等符号的运算，很有意义。
对自己又有了进一步的提高，并对数据结构这门课有更深刻的认识。
