表达式求值
时间限制：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
1 /* 2 功能Function Description: 利用栈实现中序表达式 NYOJ-35
3 开发环境Environment: DEV C++ 4.9.9.1 4 技术特点Technique: 5 版本Version: 6 作者Author: 可笑痴狂 7 日期Date: 20120802 8 备注Notes: 9 表达式 输入'='结束 支持浮点数 10 注意： 11 用exit(0) 提交会显示编译错误，没有<conin.h>头文件 12 */ 13 14 #include<cstdio> 15 #include<iostream> 16 #include<stack> 17 #include<cctype> 18 #include<cmath> 19 //#include<conio.h> //exit(0);退出程序包含在#include<conio.h> #include<stdlib.h> 20 //#include<cstdlib> 21 using namespace std; 22 23 stack<double> Opnd; //操作数栈 24 stack<char> Optr; //运算符栈 25 26 void Init() //栈的初始化 27 { 28 while(!Opnd.empty()) 29 Opnd.pop(); 30 while(!Optr.empty()) 31 Optr.pop(); 32 Optr.push('='); //先压入一个结束符‘=’ 33 } 34 35 char Precede(char i,char j) //判断i和j的优先级 36 { 37 switch(i) 38 { 39 case '+': 40 case '-': 41 if(j=='+'||j=='-'||j==')'||j=='=') 42 return '>'; 43 else 44 return '<'; 45 case '*': 46 case '/': 47 if(j=='(') 48 return '<'; 49 else 50 return '>'; 51 case '(': 52 if(j==')') 53 return '='; 54 // else if(j=='=') 55 // exit(0); 56 else 57 return '<'; 58 case ')': 59 // if(j=='(') 60 // exit(0); 61 // else 62 return '>'; 63 case '=': 64 if(j=='=') 65 return '='; 66 // else if(j==')') 67 // exit(0); 68 else 69 return '<'; 70 } 71 // exit(0); 72 } 73 74 double Operate(double a,char i,double b) //计算 75 { 76 switch (i) 77 { 78 case '+': 79 return a+b; 80 case '-': 81 return a-b; 82 case '*': 83 return a*b; 84 case '/': 85 return a/b; 86 } 87 } 88 89 int judge(char c) //判断---如果c为数字则返回1；若为小数点则返回2；如果c为操作符或者结束符则返回0；； 90 { 91 if(isdigit(c)) 92 return 1; 93 else if(c=='.') 94 return 2; 95 else 96 return 0; 97 } 98 99 double EvaluateExpression(char *p) 100 { 101 double a,b,temp; 102 int flag; 103 char *st,*end,c,theta; //定义操作符theta 104 Init(); 105 c=*p; 106 while(c!='='||Optr.top()!='=') //即当操作符栈和当前读入的字符都是‘=’时结束循环 107 { 108 if(isdigit(c)) //isdigit(c) 如果c是数字，则返回true; isalpha(c) 如果c是字母，则为true； 109 { 110 temp=0; 111 flag=0; 112 for(;judge(c);c=*(++p)) //当不是数字或小数点时结束循环 113 { 114 if(judge(c)==1) //说明是数字 115 { 116 temp=temp*10+c-'0'; 117 if(c!=0) 118 end=p; 119 } 120 else //说明是小数点 121 { 122 st=p; //记录下小数点的位置 123 end=p; //记录小数点后最后一个非零数字的位置 124 flag=1; //标记有小数点 125 } 126 } 127 if(flag) //调整小数点的位置 128 temp=temp/pow(10,end-st); 129 Opnd.push(temp); //记录的数字进栈 130 } 131 else 132 { 133 switch(Precede(Optr.top(),c)) 134 { 135 case '<': //栈顶元素优先权低 136 Optr.push(c); 137 c=*(++p); 138 break; 139 case '>': //栈顶元素优先权高---退栈并将运算结果入栈 140 theta=Optr.top(); 141 Optr.pop(); 142 a=Opnd.top(); 143 Opnd.pop(); 144 b=Opnd.top(); 145 Opnd.pop(); 146 Opnd.push(Operate(b,theta,a)); 147 break; 148 case '=': //脱括号并接收下一字符 149 Optr.pop(); 150 c=*(++p); 151 } 152 } 153 } 154 return Opnd.top(); 155 } 156 157 int main() 158 { 159 int T; 160 char s[1000]; 161 scanf("%d",&T); 162 while(T--) 163 { 164 scanf("%s",s); 165 printf("%.2lf\n",EvaluateExpression(s)); 166 } 167 return 0; 168 }/* 功能Function Description: 利用栈实现中序表达式 开发环境Environment: DEV C++ 4.9.9.1 技术特点Technique: 版本Version: 作者Author: 可笑痴狂 日期Date: 20120802 备注Notes: 表达式 输入'#'结束 只能处理整数之间的运算 */ #include<cstdio> #include<iostream> #include<stack> #include<cctype> using namespace std; stack<int> Opnd; //操作数栈 stack<char> Optr; //运算符栈 void Init() { while(!Opnd.empty()) Opnd.pop(); while(!Optr.empty()) Optr.pop(); Optr.push('#'); //将表达式起始符 } char Precede(char i,char j) { switch(i) { case '+': case '-': if(j=='+'||j=='-'||j==')'||j=='#') return '>'; else return '<'; case '*': case '/': if(j=='(') return '<'; else return '>'; case '(': if(j==')') return '='; else if(j=='#') exit(0); else return '<'; case ')': if(j=='(') exit(0); else return '>'; case '#': if(j=='#') return '='; else if(j==')') exit(0); else return '<'; } exit(0); } int Operate(int a,char i,int b) { switch (i) { case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; } } int EvaluateExpression(char *p) { int a,b,temp; char c,theta; //定义操作符theta Init(); c=*p; while(c!='#'||Optr.top()!='#') { if(isdigit(c)) //isdigit(c) 如果c是数字，则返回true; isalpha(c) 如果c是字母，则为true； { temp=0; for(;isdigit(c);c=*(++p)) temp=temp*10+(c-'0'); Opnd.push(temp); //检测到有运算符，先把记录的数字进栈 } else { switch(Precede(Optr.top(),c)) { case '<': //栈顶元素优先权低 Optr.push(c); c=*(++p); break; case '>': //栈顶元素优先权高---退栈并将运算结果入栈 theta=Optr.top(); Optr.pop(); a=Opnd.top(); Opnd.pop(); b=Opnd.top(); Opnd.pop(); Opnd.push(Operate(b,theta,a)); break; case '=': //脱括号并接收下一字符 Optr.pop(); c=*(++p); } } } return Opnd.top(); } int main() { int T; char s[1000]; scanf("%d",&T); while(T--) { scanf("%s",s); printf("%d\n",EvaluateExpression(s)); } return 0; }