题目描述
模拟计算机处理算术表达式过程,从键盘上输入算术表达式串,表达式只包括'+','-','*','/'四种运算符,数字和括号,其中'-'只表示减号,不表示负数,即表达式里不存在负数,'/'如果不能整除,结果只取商,保证输入的字符串是合法的,求出该表达式的值
输入格式
只有一行为一个表达式,长度小于100
输出
只有一行,为表达式的值
样例输入
(123+321)*(2-3)/5
样例输出
-88
【算法分析】
用两个栈来存储,一个栈存储数,另外一个栈存储运算符,转换完了,再对运算符栈逐一出栈,出一个运算符,就把数值所在的栈的栈顶的两元素进行运算结果存在栈顶(栈顶两元素,一个出栈,另一个更新成运算后的结果)。这里要注意优先性的问题
【代码实现】
#include<bits/stdc++.h>
using namespace std;
int number[101],i=0, p=1;
char symbol[101],s[256], t[256];
void push() //算符入栈运算
{symbol[++p]=s[i];}
void pop() //运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算
{switch (symbol[p--])//注意这里p退了一步,symbol[p];p--;{case '+':number[p]+=number[p+1];break;case '-':number[p]-=number[p+1];break;case '*':number[p]*=number[p+1];break;case '/':number[p]/=number[p+1];break;}}
bool can() //判断运算符的优先级别,建立标志函数
{if ((s[i]=='+'||s[i]=='-')&&symbol[p]!='(') return 1;//这里能体现+-*/优先性if ((s[i]=='*'||s[i]=='/')&&(symbol[p]=='*'||symbol[p]=='/'))return 1;return 0;
}
main()
{printf("String :");gets(s);s[strlen(s)]=')';symbol[p]='(';while (i<strlen(s))
{while (s[i]=='(') //左括号处理{push();i++;}int x=0;while (s[i]>='0'&&s[i]<='9') //取数入操作数栈x=x*10+s[i++]-'0';number[p]=x;do{if (s[i]==')') //右括号处理{while (symbol[p]!='(') pop();//这里是此题难点且关键number[--p]=number[p + 1];}else{//根据标志函数值作运算符入栈或出栈运算处理while (can()) pop();push();}for(int j=0;j<=i+1;j++)cout<<number[j]<<" ";cout<<endl;for(int j=0;j<=i+1;j++)cout<<symbol[j]<<" ";cout<<endl;i++;}while(i<strlen(s)&&s[i-1]==')');}printf("Result=%d", number[0]);return 0;
}