利用栈来实现算术表达式求值

本文主要是介绍利用栈来实现算术表达式求值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

通过修改完善教材中的算法3.4，利用栈来实现算术表达式求值的算法。对算法3.4中调用的几个函数要给出其实现过程：
(1) 函数In©：判断c是否为运算符；
(2) 函数Precede(t1,t2)：判断运算符t1和t2的优先级；
(3) 函数Operate(a,theta,b)：对a和b进行二元运算theta。
程序运行时，输入合法的算术表达式（中间值及最终结果要在0～9之间，可以包括加减乘除和括号）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"stack.h"#define N 1000+10char str[N];unsigned char prior[7][7] = {
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'<','<','<','<','<',' ','>'},
{'<','<','<','<','<',' ','='}};char OPSET[7] = {'+','-','*','/','(',')','#'};Status In(char c,char str[])//判断是否为运算符 
{int i = 0;while(c != str[i]){i++;}if(i < 7)return OK;return ERROR;
}void  Strcat(char *str1,char *str2)//字符串连接函数，把字符串str2连接到str1后 
{int i = 0, j = 0;while(str1[i]!='\0'){i++;}while(str2[j]!='\0'){str1[i++] = str2[j++];}str1[i] = '\0';
} Status Atoi(char *c)//把字符串转为数字 
{int data= 0,d = 0;int i = 0;while(c[i]!='\0'){data = data*10 + c[i]-'0';i++;}return data;	
} Status precede(int a,char b)//判断优先级函数 
{int i = 0,j = 0;while(OPSET[i] != a){i++;}while(OPSET[j] != b){j++;}return prior[i][j];
}Status Opereta(int a,int b,int c)//运算函数 
{switch(b){case '+':return a+c;case '-':return a-c;case '*':return a*c;case '/':return a/c;} return OK;
}int EvaluateExpression(char *MyExpression)//算法3.4 
{//算术表达式求值的算符优先算法。
//设OPTR和OPND分别为运算符栈和运算数栈SqStack OPTR;//运算符栈，字符元素 SqStack OPND;//运算数栈，实数元素 char TempData[20];int data,a,b;char *c,Dr[2],e;int theta;InitStack(&OPTR);Push(&OPTR,'#');InitStack(&OPND);c = MyExpression;TempData[0] = '\0';while(*c != '#'|| GetTop(&OPTR) != '#'){if(!In(*c,OPSET))//不是运算符则进栈 {Dr[0] = *c;Dr[1] = '\0';Strcat(TempData,Dr);c++; if(In(*c,OPSET))//是运算符时 {data = Atoi(TempData);Push(&OPND,data);TempData[0] = '\0';}}else{switch(precede(GetTop(&OPTR),*c)){case '<':Push(&OPTR,*c);c++;break;case '=':Pop(&OPTR);c++;break;case '>':a = Pop(&OPND);b = Pop(&OPND);theta = Pop(&OPTR);Push(&OPND,Opereta(b,theta,a));break;}}}return GetTop(&OPND);
}
int main()
{printf("请输入表达式:");while(scanf("%s",str)!=EOF){printf("%d\n\n",EvaluateExpression(str));printf("请输入表达式:");}return 0;}