35-表达式求值

 

内存限制:64MB 时间限制:3000ms 特判: No 通过数:111 提交数:210 难度:4

 

题目描述:

ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。 比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）

输入描述:

第一行输入一个整数n，共有n组测试数据（n<10)。 每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。 数据保证除数不会为0

输出描述:

每组都输出该组运算式的运算结果，输出结果保留两位小数。

样例输入:

2 1.000+2/4= ((1+2)*5+1)/4=

样例输出:

1.50 4.00

被这道题卡成狗，原因竟然是……

思路：

方法一：按运算符优先级来算，开两个栈，num存数字，fu存符号

（1）'('  入栈

（2）')'  进行运算，直到'('出栈

（3）数字，进数字栈（我算数字，小数的时候除的10，定义成int了，wa了一年）

（4）符号，判断栈顶优先级，必须优先级大于栈顶才能入栈，否则运算

等于也不行，因为要遵循从左到右的原则呀

#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<stack> using namespace std; typedef pair<char,int> P; char s[1005]; map<char,int>pi; stack<double>num; stack<char>fu; void cal(char f){ double t1=num.top();num.pop(); double t2=num.top();num.pop(); if(f=='+'){ num.push(t1+t2); } if(f=='-'){ num.push(t2-t1); } if(f=='*'){ num.push(t1*t2); } if(f=='/'){ num.push(t2/t1); } } int main(){ int t; pi.insert(P('(',0)); pi.insert(P('+',1)); pi.insert(P('-',1)); pi.insert(P('*',2)); pi.insert(P('/',2)); scanf("%d",&t); while(t--){ scanf("%s",s); int len=strlen(s); for(int i=0;i<len-1;){//左括号直接入栈 if(s[i]=='('){ fu.push(s[i]); i++; } else if(s[i]>='0'&&s[i]<='9'||s[i]=='.'){//数字求值，入栈 double n=0; int flag=0; double q=10; while(s[i]>='0'&&s[i]<='9'||s[i]=='.'&&i<len-1){ if(s[i]=='.'){ flag=1; i++; continue; } if(!flag){ n=n*10+s[i]-'0'; } else{ n=n+(s[i]-'0')/q; q*=10; } i++; } num.push(n); } else if(s[i]==')'){//右括号，计算 char f=fu.top(); while(f!='('){ cal(f); fu.pop(); f=fu.top(); } fu.pop(); i++; } else{//运算符号 if(fu.empty()){ fu.push(s[i]); } else{ char f=fu.top(); if(pi[f]<pi[s[i]]){//符号优先级大于等于栈顶符号优先级 fu.push(s[i]); } else{//优先级小，计算 while(pi[f]>=pi[s[i]]){ cal(f); fu.pop(); if(fu.size()==0)break; f=fu.top(); } fu.push(s[i]); } } i++; } } while(fu.size()){ char f=fu.top(); cal(f); fu.pop(); } printf("%.2f\n",num.top()); num.pop(); } }

方法二：来自这位老哥

也就是把字符串先转成逆波兰式，再求值

#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<stack> using namespace std; typedef pair<char,int> P; const int N=1005; string s1,s2; map<char,int>pi; void change(){ stack<char>s; s.push('#'); int i=0,len=s1.length(); while(i<len-1){ if(s1[i]=='('){ s.push(s1[i++]); } else if(s1[i]==')'){ while(s.top()!='('){ s2+=s.top(); s2+=' '; s.pop(); } s.pop(); i++; } else if(s1[i]=='+'||s1[i]=='-'||s1[i]=='*'||s1[i]=='/'){ while(pi[s.top()]>=pi[s1[i]]){ s2+=s.top(); s2+=' '; s.pop(); } s.push(s1[i]); i++; } else{ while(i<len-1&&(s1[i]>='0'&&s1[i]<='9'||s1[i]=='.')){ s2+=s1[i++]; } s2+=' '; } } while(s.top()!='#'){ s2+=s.top(); s2+=' '; s.pop(); } } double value(){ stack<double> s; double x,y; int i = 0,len=s2.length(); while(i<len){ if(s2[i]==' '){ i++; continue; } switch(s2[i]){ case '+': x = s.top();s.pop();x+=s.top();s.pop();i++;break; case '-': x = s.top();s.pop();x=s.top()-x;s.pop();i++;break; case '*': x = s.top();s.pop();x*=s.top();s.pop();i++;break; case '/': x = s.top();s.pop();x=s.top()/x;s.pop();i++;break; default:{ x=0; int flag=0; double q=10; while(i<len&&(s2[i]>='0'&&s2[i]<='9'||s2[i]=='.')){ if(s2[i]=='.'){ flag=1; i++; continue; } if(!flag){ x=x*10+s2[i]-'0'; } else{ x=x+(s2[i]-'0')/q; q*=10; } i++; } } } s.push(x); } return s.top(); } int main(){ int t; scanf("%d",&t); pi.insert(P('(',0)); pi.insert(P('+',1)); pi.insert(P('-',1)); pi.insert(P('*',2)); pi.insert(P('/',2)); while(t--){ cin>>s1; s2=""; change(); double res=value(); printf("%.2f\n",res); } }