表达式求值
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
- 假设表达式定义为:1. 一个十进制的正整数 X 是一个表达式。2. 如果 X 和 Y 是 表达式，则 X+Y, X*Y 也是表达式; *优先级高于+.3. 如果 X 和 Y 是 表达式，则 函数 Smax(X,Y)也是表达式,其值为:先分别求出 X ,Y值的各位数字之和，再从中选最大数。4．如果 X 是 表达式，则 （X）也是表达式。 例如:表达式 12*(2+3)+Smax(333,220+280) 的值为 69。 请你编程，对给定的表达式，输出其值。
- 输入
- 【标准输入】 第一行： T 表示要计算的表达式个数 （1≤ T ≤ 10） 接下来有 T 行， 每行是一个字符串，表示待求的表达式，长度<=1000
- 输出
- 【标准输出】 对于每个表达式，输出一行，表示对应表达式的值。
- 样例输入
-
3 12+2*3 12*(2+3) 12*(2+3)+Smax(333,220+280)
- 样例输出
-
18 60 69
- 来源
- 河南省第九届省赛
大致思路：
- 用stack来实现的后缀表达式的解法。
- 每次需要考虑运算符的优先级，怎么考虑？
- 分类讨论：
- 1、顺序遍历表达式，当前符号位为加号时，判断上一位，是加号（同级），取num栈两个栈顶元素和op栈栈顶符号进行一次运算，再放回num栈中。
- 2、当前符号位为乘号，如果乘号的前后都是数字——那么一定可以进行乘法运算一次；由于在顺序遍历数组时，不方便预知后面一位是否为数字，可以在每次读入一位数字后进行判断；乘号的前后都是数字时，可以放心做乘。
- 3、当前符号位为S，Smax可以特殊处理，不存入“Smax”，只保留中间的', ' 即可！把', ' 号当做特殊运算符（类似与‘*’和‘+’）。
- 4、遇见左括号，存入；遇见右括号，开始进行计算一直计算到左括号，并把左括号删除。还有就是第三步', '的左右，进行运算时——要确保‘，’左右两边都是一个确定的数值！不然没法运算，所以对‘，’左边必须进行处理成一个整数！
- 5、加强版的样例 ：
-
21
1+2
1+2+3
12*3+4*1*2
12*(1+3*4+1)12*(2+3*1)+Smax(333,220*1+280)
12*(2+3)+(1+1*333,220*1+280)题解：（有稍微的注释）
View Code1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string> 7 #include<stdlib.h> 8 #include<map> 9 #include<stack> 10 #include<queue> 11 #define inf 0x3f3f3f3f//19:04-- 12 #define N 1008 13 #define ll long long 14 using namespace std; 15 stack<int>num; 16 stack<char>op; 17 char str[N]; 18 void cal(char opx){//依据opx来计算num栈上的前两位 19 if(num.size()<=1)return ; 20 int n1,n2; 21 n1=num.top();num.pop(); 22 n2=num.top();num.pop(); 23 if(opx=='*') 24 num.push(n1*n2); 25 else if(opx=='+') 26 num.push(n1+n2); 27 else if(opx==','){ 28 int s1=0,s2=0; 29 while(n1>0){ 30 s1+=n1%10;n1/=10; 31 } 32 while(n2>0){ 33 s2+=n2%10;n2/=10; 34 } 35 num.push(max(s1,s2)); 36 } 37 } 38 void cal2(char opx){//计算到左括号为止（Smax可以特殊处理：只保留中间的','即可！把','号当做特殊运算符） 39 if(opx==','){ 40 while(op.top()!='('){ 41 cal(op.top()); 42 op.pop(); 43 } 44 // op.pop(); 45 46 }else{ 47 while(op.top()!='('){ 48 cal(op.top()); 49 op.pop(); 50 } 51 op.pop();//去掉左括号 52 } 53 } 54 int get_nextnum(int i){//分离出从str[]数组下标i开始的数字，注意要返回j 55 int j,sum=str[i]-'0'; 56 for(j=i+1;j<strlen(str);j++){ 57 if(str[j]>='0'&&str[j]<='9') 58 sum=sum*10+str[j]-'0'; 59 else 60 break; 61 } 62 num.push(sum); 63 return j; 64 } 65 66 void solve(){ 67 int ans=0; 68 int len=strlen(str); 69 for(int i=0;i<len;){ 70 if(str[i]==' ') 71 i++; 72 else if(str[i]>='0'&&str[i]<='9'){ 73 i=get_nextnum(i);//获取该位置数字 74 if(!op.empty()&&op.top()=='*'){//当读入一个数字后，发现上一位是乘号：及时做乘 75 cal('*'); 76 op.pop(); 77 } 78 } 79 else if(str[i]=='*'){ 80 op.push('*'); 81 i++; 82 } 83 else if(str[i]=='+'){ 84 if(!op.empty()&&op.top()=='+'){ 85 cal(str[i]);//可以省略一push一次‘+’，毕竟先pop‘+’后push‘+’ 86 } 87 else if(!op.empty()&&op.top()=='*'){ 88 cal('*'); 89 op.pop(); 90 op.push('+'); 91 } 92 else 93 op.push('+'); 94 i++; 95 } 96 else if(str[i]=='S'){ 97 i+=4; 98 } 99 else if(str[i]==','){ 100 cal2(',');//计算到左括号！ 101 op.push(str[i++]); 102 } 103 else if(str[i]=='('){ 104 op.push(str[i++]); 105 } 106 else if(str[i]==')'){ 107 cal2(')'); 108 i++; 109 } 110 } 111 112 while(op.size()>=1){ 113 cal(op.top()); 114 op.pop(); 115 } 116 117 ans=num.top(); 118 119 printf("%d ",ans); 120 } 121 122 int main(){ 123 int T; 124 scanf("%d ",&T); 125 126 while(T--){ 127 while(num.size()>0)num.pop();//清空整个num栈和op栈 128 while(op.size()>0)op.pop(); 129 gets(str); 130 solve(); 131 } 132 133 return 0; 134 }
