算法训练 表达式计算

算法训练 表达式计算   时间限制：1.0s   内存限制：256.0MB      问题描述 　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 　　输入一行，包含一个表达式。 输出格式 　　输出这个表达式的值。 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定 　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

 

这道题从很久之前就开始想，思考了很久，想着用链表用栈，最终在别人的代码的指导下解出来了

以前也写过大位数计算器，现在想想当时真的是不可思议，竟然写出来了那么复杂的大位数四则运算

简单说下这道题，应该是在那个地方看到过这种建两个栈完成四则运算的 

两个栈一个是字符栈一个是数字栈

首先呢要讲第一个字符存入（，对以后的字符的计算有帮助。

假设2*（2-3）

首先存入数字栈存入2，字符栈存入*，在*之前判断是否有需要计算的*号优先级以上或者相同的除了（

然后存入（，再在数字栈中存入2，字符栈中存入-，存-前判断

存入3，遇到）可以弹出了并计算已有的数字串的计算

详见

其实主要的意思是遇到的情况按照优先顺序从左向右走

#include <cstdio> #include <cstring> #include <stack> #include <iostream> using namespace std; stack<int>Num; stack<int>S; int cal(int x,int y,char n) { switch(n) { case '+': return x+y; case '-': return x-y; case '*': return x*y; case '/': return x/y; } return 0; } void calculate1() { char n=S.top(); while(n!='(') { S.pop(); int n1=Num.top(); Num.pop(); int n2=Num.top(); Num.pop(); int n3=cal(n2,n1,n); //printf("%d\n",n3); Num.push(n3); n=S.top(); } } void calculate2() { char n=S.top(); if(n=='*'||n=='/') { S.pop(); int n1=Num.top(); Num.pop(); int n2=Num.top(); Num.pop(); int n3=cal(n2,n1,n); //printf("%d\n",n3); Num.push(n3); } } int main() { char str[105]; gets(str); char c[2]="."; strcat(str,c); S.push('('); int num=0; int l=strlen(str); for(int i=0;i<l;i++) { if(str[i]>='0'&&str[i]<='9') { num=num*10+str[i]-'0'; if(str[i+1]<'0'||str[i+1]>'9') { Num.push(num); num=0; } } else { switch(str[i]) { case '+': calculate1(); S.push('+'); break; case '-': calculate1(); S.push('-'); break; case '*': calculate2(); S.push('*'); break; case '/': calculate2(); S.push('/'); break; case '(': S.push('('); break; case ')': calculate1(); S.pop(); break; case '.': calculate1(); S.pop(); break; } } } printf("%d\n",Num.top()); return 0; }