利用栈实现四则运算表达式的高效求值方法

要求从键盘输入一个算术表达式并输出它的结果&＃xff0c;算术表达式可包含加、减、乘、除、十进制整数和小括号&＃xff0c;利用栈实现。

首先我们需要定义两个栈的基本创建插入删除操作
数据栈&＃xff1a;存放数据
操作符栈&＃xff1a;存放操作符

#include
#include
typedef int ElemType;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct //定义数据栈(存放数据)
{ ElemType *base;ElemType *top;int stacksize;}SqStack; typedef struct //定义操作符栈 { char *base;char *top;int stacksize;}OpStack;
int InitStack(SqStack &s) //初始化数据栈
{ s.base&＃61;(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!s.base) return 0;s.top&＃61;s.base;s.stacksize&＃61;STACK_INIT_SIZE;return 1;} int Push(SqStack &s,ElemType e) //数据栈的进栈操作 { if(s.top-s.base>&＃61;s.stacksize){s.base&＃61;(ElemType *)realloc(s.base,(s.stacksize&＃43;STACKINCREMENT)*sizeof(ElemType)); if(!s.base) return 0;s.top&＃61;s.base&＃43;s.stacksize;s.stacksize&＃43;&＃61;STACKINCREMENT;}*s.top&＃43;&＃43;&＃61;e;return 1;}int Pop(SqStack &s,ElemType &e) //数据栈的出栈操作 { if(!s.base) return 0;e&＃61;*--s.top;return 1;}int InitOpStack(OpStack &s) //初始化操作符栈
{ s.base&＃61;(char *)malloc(STACK_INIT_SIZE*sizeof(char));if(!s.base) return 0;s.top&＃61;s.base;s.stacksize&＃61;STACK_INIT_SIZE;return 1;} int OpPush(OpStack &s,char e) //操作符栈的进栈操作 { if(s.top-s.base>&＃61;s.stacksize){s.base&＃61;(char *)realloc(s.base,(s.stacksize&＃43;STACKINCREMENT)*sizeof(char)); if(!s.base) return 0;s.top&＃61;s.base&＃43;s.stacksize;s.stacksize&＃43;&＃61;STACKINCREMENT;}*s.top&＃43;&＃43;&＃61;e;return 1;}int OpPop(OpStack &s,char &e) //操作符栈的出栈操作 { if(!s.base) return 0;e&＃61;*--s.top;return 1;}

然后定义一个运算符比较表来告诉系统这些基本运算符的优先顺序。

char Precede(char a1,char a2) //运算符比较表 { switch(a1){case &＃39;&＃43;&＃39;:switch(a2){case &＃39;&＃43;&＃39;:return &＃39;>&＃39;;case &＃39;-&＃39;:return &＃39;>&＃39;;case &＃39;*&＃39;:return &＃39;<&＃39;;case &＃39;/&＃39;:return &＃39;<&＃39;;case &＃39;(&＃39;:return &＃39;<&＃39;;case &＃39;)&＃39;:return &＃39;>&＃39;;case &＃39;#&＃39;:return &＃39;>&＃39;;}case &＃39;-&＃39;:switch(a2){case &＃39;&＃43;&＃39;:return &＃39;>&＃39;;case &＃39;-&＃39;:return &＃39;>&＃39;;case &＃39;*&＃39;:return &＃39;<&＃39;;case &＃39;/&＃39;:return &＃39;<&＃39;;case &＃39;(&＃39;:return &＃39;<&＃39;;case &＃39;)&＃39;:return &＃39;>&＃39;;case &＃39;#&＃39;:return &＃39;>&＃39;;}case &＃39;*&＃39;:switch(a2){case &＃39;&＃43;&＃39;:return &＃39;>&＃39;;case &＃39;-&＃39;:return &＃39;>&＃39;;case &＃39;*&＃39;:return &＃39;>&＃39;;case &＃39;/&＃39;:return &＃39;>&＃39;;case &＃39;(&＃39;:return &＃39;<&＃39;;case &＃39;)&＃39;:return &＃39;>&＃39;;case &＃39;#&＃39;:return &＃39;>&＃39;; }case &＃39;/&＃39;:switch(a2){case &＃39;&＃43;&＃39;:return &＃39;>&＃39;;case &＃39;-&＃39;:return &＃39;>&＃39;;case &＃39;*&＃39;:return &＃39;>&＃39;;case &＃39;/&＃39;:return &＃39;>&＃39;;case &＃39;(&＃39;:return &＃39;<&＃39;;case &＃39;)&＃39;:return &＃39;>&＃39;;case &＃39;#&＃39;:return &＃39;>&＃39;;}case &＃39;(&＃39;:switch(a2){case &＃39;&＃43;&＃39;:return &＃39;<&＃39;;case &＃39;-&＃39;:return &＃39;<&＃39;;case &＃39;*&＃39;:return &＃39;<&＃39;;case &＃39;/&＃39;:return &＃39;<&＃39;;case &＃39;(&＃39;:return &＃39;<&＃39;;case &＃39;)&＃39;:return &＃39;&＃61;&＃39;;case &＃39;#&＃39;:return 0;}case &＃39;)&＃39;:switch(a2){case &＃39;&＃43;&＃39;:return &＃39;>&＃39;;case &＃39;-&＃39;:return &＃39;>&＃39;;case &＃39;*&＃39;:return &＃39;>&＃39;;case &＃39;/&＃39;:return &＃39;>&＃39;;case &＃39;(&＃39;:return 0;case &＃39;)&＃39;:return &＃39;>&＃39;;case &＃39;#&＃39;:return &＃39;>&＃39;;}case &＃39;#&＃39;:switch(a2){case &＃39;&＃43;&＃39;:return &＃39;<&＃39;;case &＃39;-&＃39;:return &＃39;<&＃39;;case &＃39;*&＃39;:return &＃39;<&＃39;;case &＃39;/&＃39;:return &＃39;<&＃39;;case &＃39;(&＃39;:return &＃39;<&＃39;;case &＃39;)&＃39;:return 0;case &＃39;#&＃39;:return &＃39;&＃61;&＃39;;}}}


定义函数&＃xff08;对从栈顶取出的两个数进行操作&＃xff09;

ElemType Operate(ElemType a,char theta,ElemType b) //两个数的操作
{ ElemType sum;switch(theta) //对传递的运算符进行相应操作 { case &＃39;&＃43;&＃39;:sum&＃61;a&＃43;b;break;case &＃39;-&＃39;:sum&＃61;a-b;break;case &＃39;*&＃39;:sum&＃61;a*b;break;case &＃39;/&＃39;:sum&＃61;a/b;break; }return sum;
}


然后通过表达式求值算法函数调用前面所说函数进行计算

int EvaluateExpression() //表达式求值 { SqStack OPND;OpStack OPTR;int flag&＃61;0; //标志变量 判断连续进数字栈的个数 char c,e,theta; //c为输入字符 e&＃xff0c;theta为下面删除变量 ElemType b,a; //ba为下面的删除变量 InitOpStack(OPTR);OpPush(OPTR,&＃39;#&＃39;); //初始化两个栈 并且将#进入操作符栈底 InitStack(OPND);printf("输入表达式(输入#结束)&＃xff1a;\n");c&＃61;getchar();while(c!&＃61;&＃39;#&＃39;||*(OPTR.top-1)!&＃61;&＃39;#&＃39;) //当输入的字符不为#或者操作符栈顶指针不指向栈底 { if(c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;) //如果字符为数字 { Push(OPND,c-48); //进数字栈 if(flag!&＃61;0) //如果数字高于10位数 { Pop(OPND,b);Pop(OPND,a);Push(OPND,a*10&＃43;b); //把计算出来的结果重新入栈 flag&＃61;0;}flag&＃61;1;c&＃61;getchar();}else //如果为运算符 {switch(Precede(*(OPTR.top-1),c)) //比较操作符栈顶指针与输入字符优先级 { case &＃39;<&＃39;:OpPush(OPTR,c);flag&＃61;0;c&＃61;getchar();break;//如果小于 继续进栈 case &＃39;&＃61;&＃39;:OpPop(OPTR,e);flag&＃61;0;c&＃61;getchar();break; //等于 删除 case &＃39;>&＃39;:OpPop(OPTR,theta);flag&＃61;0;Pop(OPND,b);Pop(OPND,a); //大于 提取数字栈顶的两个数进行运算 Push(OPND,Operate(a,theta,b)); //将运算完成的数进栈 break;}}}printf("表达式的值&＃61;:%d",*(OPND.top-1)); return 1;}


然后在主函数中调用&＃xff0c;查看运行结果

int main(){ EvaluateExpression();return 0;}