表达式求值
时间限制：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
中缀转后缀，计算后缀
001.#include
<iostream>002.#include
<stack>003.#include
<string>004.#include
<stdlib.h>005.#include
<sstream>006.#include
<stdio.h>007.using namespace std;008. 009. 010. 011.string
Infix2Postfix(string &s)012.{013.string
d;014.stack<char>
sc;015.for(int i=0;i<s.size()-1;i++)016.{017.if(s[i]=='+'||s[i]=='-')018.{019.if((d[d.size()-1]>='0'&&d[d.size()-1]<='9')||d[d.size()-1]=='.')020.d+='
';021.while(!sc.empty())022.{023.if(sc.top()=='(')024.{025.break;026.}027.d+=sc.top();028.d+='
';029.sc.pop();030.}031.sc.push(s[i]);032.}033.else if(s[i]=='*'||s[i]=='/')034.{035.if((d[d.size()-1]>='0'&&d[d.size()-1]<='9')||d[d.size()-1]=='.')036.d+='
';037.while(!sc.empty())038.{039.if(sc.top()=='*'||sc.top()=='/')040.{041.d+=sc.top();042.d+='
';043.sc.pop();044.}045.else046.break;047.}048.sc.push(s[i]);049.}050.else if(s[i]=='(')051.sc.push(s[i]);052.else if(s[i]==')')053.{054.if((d[d.size()-1]>='0'&&d[d.size()-1]<='9')||d[d.size()-1]=='.')055.d+='
';056.while(!sc.empty())057.{058.if(sc.top()=='(')059.{060.sc.pop();061.break;062.}063.d+=sc.top();064.d+='
';065.sc.pop();066.}067.}068.else069.{070.d+=s[i];071.}072.}073.if((d[d.size()-1]>='0'&&d[d.size()-1]<='9')||d[d.size()-1]=='.')074.d+='
';075.while(!sc.empty())076.{077.d+=sc.top();078.d+='
';079.sc.pop();080.}081.return d;082.}083. 084.double CalPostfix(string
s)085.{086.stack<double>
sd;087.stringstream
sstrm(s);088.string
tmp;089.double a,b;090.while(sstrm>>tmp)091.{092.if(tmp=="+")093.{094.a=sd.top();095.sd.pop();096.b=sd.top();097.sd.pop();098.sd.push(a+b);099.}100.else if(tmp=="-")101.{102.a=sd.top();103.sd.pop();104.b=sd.top();105.sd.pop();106.sd.push(b-a);107.}108.else if(tmp=="*")109.{110.a=sd.top();111.sd.pop();112.b=sd.top();113.sd.pop();114.sd.push(a*b);115.}116.else if(tmp=="/")117.{118.a=sd.top();119.sd.pop();120.b=sd.top();121.sd.pop();122.sd.push(b/a);123.}124.else125.sd.push(atof(tmp.c_str()));126.}127.return sd.top();128.}129. 130.int main()131.{132.int n;133.string
infix,postfix;134.double ans;135.cin>>n;136.while(n--)137.{138.cin>>infix;139.postfix=Infix2Postfix(infix);140.ans=CalPostfix(postfix);141.printf("%.2f\n",ans);142.//cout<<ans<<endl;143.//cout<<postfix<<endl;144.}145.return 0;146.}