NYOJ - 表达式求值(逆波兰式)_综合

表达式求值

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 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

/*
*    这里主要是逆波兰式的实现，使用两个stack 这里用字符串来模拟一个stack，第一步，将中缀表达式转变为后缀表达式
*    第二步，然后再使用一个stack，计算后缀表达式的结果，这一步很容易出错，考虑到浮点数的问题。
*/
#include <iostream>
#include <string>
#include <stack>
#include <iomanip>using namespace std;int cmp(char ch)     // 运算符优先级 
{switch(ch){case '+':case '-': return 1;case '*':case '/': return 2;default : return 0;}
}
void change(string &s1, string &s2)       // 中缀表达式转变后缀表达式 
{stack <char > s;s.push('#');int i = 0;while(i < s1.length()-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(cmp(s.top()) >= cmp(s1[i])){s2 += s.top();s2 += ' ';s.pop();}s.push(s1[i]);i++;}else{while('0' <= s1[i]&&s1[i] <= '9'||s1[i] == '.'){s2 += s1[i++];}s2 += ' ';}}while(s.top() != '#'){s2 += s.top();s2 += ' ';s.pop();}
}double value(string s2)         // 计算后缀表达式，得到其结果。 
{stack < double> s;double x,y;int i = 0;while(i < s2.length()){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;while('0' <= s2[i]&&s2[i] <= '9'){x = x*10+s2[i] - '0';i++;}if(s2[i] == '.'){double k = 10.0;y = 0;i++;while('0' <= s2[i]&&s2[i] <= '9'){y += ((s2[i]-'0')/k);i++;k *= 10;}x += y;}}}s.push(x);}return s.top();
}
int main(int argc, char const *argv[])
{int n;string s1,s2;cin>>n;while(n--){cin>>s1;s2 = "";change(s1,s2);cout<<fixed<<setprecision(2)<<value(s2)<<endl;}return 0;
}