时间限制：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来源
数据结构课本例题改进
上传者
张云聪
/* nyoj-35 表达式计算(中缀式求值) */ #include <stdio.h> #include <string.h> #include <ctype.h> #include <stack> #define N 1050 using namespace std; char s[N]; stack<double>Num; // 数据栈 stack<char>Ope; // 符号栈 double JiSuan(){ // 计算函数，自身从栈中取数据 double b = Num.top(); Num.pop(); double a = Num.top(); Num.pop(); char c = Ope.top(); Ope.pop(); switch(c){ case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; } } double JieXi(){ // 解析函数 int i = -1, ni = 0; // i为输入表达式（字符串）下标 ，ni为num数组下标； char num[100] = {"\0"}; // 暂存数字字符和小数点，用于将字符串转换为数字 double ans = 0; // 记录每一次计算的结果 while(1){ i ++; if(isdigit(s[i]) || s[i] == '.'){ // 如果当前字符是数字或小数点，将其直接放入数字暂存数组 num[ni ++] = s[i]; } else{ // 当前字符为运算符 if(ni != 0){ // 如果数字暂存数组中有数据，转换成数字，并压入数据栈 sscanf(num, "%lf", &ans); Num.push(ans); memset(num, '\0', sizeof(num)); // 入栈后清空暂存数组，其下标置零 ni = 0; } switch(s[i]){ // 分析运算符，并开始计算 case '+': case '-': case '=': while(!Ope.empty() && Ope.top() != '('){ // 其它运算符优先级都高于+、-、=，先全部运算直至符号栈栈顶为'('或栈空 ans = JiSuan(); Num.push(ans); // 记得将运算结果压入数据栈，当前运算符break后压入 } break; case '*': case '/': while(!Ope.empty() && (Ope.top() == '*' || Ope.top() == '/')){ ans = JiSuan(); Num.push(ans); } break; case ')': while(Ope.top() != '('){ // 运算直至符号栈栈顶为( ans = JiSuan(); Num.push(ans); } Ope.pop(); // 将栈顶的(弹出 break; case '(': // ( 之后直接如符号栈即可，无需运算 break; } if(s[i] == '='){ Num.pop(); // 此次弹出后，数据栈已清空;并且在之前运算中符号栈已清空（有运算符就有运算） break; // 运算结束 } else{ if(s[i] != ')'){ // )、=不入栈，其余运算符都入栈 Ope.push(s[i]); } } } } return ans; } int main() { int loop; scanf("%d", &loop); while(loop --){ scanf(" %s", s); double ans = JieXi(); printf("%.2lf\n", ans); } return 0; }
//中缀表达式—后缀表达式 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <stack> using namespace std; stack<char> osta;//定义一个char类型的字符栈 stack<double> dsta;//定义一个double类型的数据栈 int main() { int T; scanf("%d",&T); while(T--) { char s[1030]; scanf("%s",&s[1]);//从下标1开始读入 int len=strlen(&s[1]); s[0]='(';s[len]=')';//把读入的表达式左端用“（”括起来，右端的等号换成“）” for(int i=0;i<=len;i++) { if(s[i]=='(') osta.push(s[i]);//是左括号则压入字符栈中 else if(s[i]>='0'&&s[i]<='9') { int b,K=0; double v=0; while(s[i]>='0'&&s[i]<='9'||s[i]=='.') { if(s[i]=='.')//判断是否是小数点 { b=i;//记录小数点的位置 K=1;//标记 } else v=v*10+s[i]-'0'; i++; } i--; if(K==1) dsta.push(v/pow(10,i-b)); else dsta.push(v); } else if(s[i]=='+'||s[i]=='-') { while(osta.top()!='(')//判断栈顶元素，同下 { double a=dsta.top();dsta.pop(); double b=dsta.top();dsta.pop(); double c; switch(osta.top()) { case '+':c=b+a;break; case '-':c=b-a;break; case '*':c=b*a;break; case '/':c=b/a;break; } dsta.push(c); osta.pop(); } osta.push(s[i]); } else if(s[i]=='*'||s[i]=='/') { if(osta.top()=='*') { double a=dsta.top();dsta.pop(); double b=dsta.top();dsta.pop(); dsta.push(b*a); osta.pop(); } else if(osta.top()=='/') { double a=dsta.top();dsta.pop(); double b=dsta.top();dsta.pop(); dsta.push(b/a); osta.pop(); } osta.push(s[i]); } else if(s[i]==')') { while(osta.top()!='(') { double a=dsta.top();dsta.pop(); double b=dsta.top();dsta.pop(); double c; switch(osta.top()) { case '+':c=b+a;break; case '-':c=b-a;break; case '*':c=b*a;break; case '/':c=b/a;break; } dsta.push(c); osta.pop(); } osta.pop(); } } printf("%.2lf\n",dsta.top()); dsta.pop();//弹出最后数据，以免影响下一次运算 } return 0; }
