表達式求值
時間限制： 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
來源
河南省第九屆省賽
這道題表達式求值題類似于nyoj35和nyoj305.這道題多了個Smax運算，其實思路都是一樣的，就是把Smax的優先級定為最高的就行，同樣有兩種解題思路，一是先把中綴表達式轉化為字尾表達式，再進行運算，第二種是在進行周遊表達式的時候就進行計算：
代碼1：
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int maxn= 1000+ 5;
string s1,s2;
stack< char> s;
stack< double> c;
void init()
{
///對兩個棧進行初始化
while(!s.empty())
s.pop();
while(!c.empty())
c.pop();
}
int pro( char ch)
{
///規定運算符的優先級
switch(ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case 'S':
return 3;
default :
return 0;
}
}
void deal()
{
init();
int i= 0,len=s1.length();
s.push( '#');
while(i<len)
{
if(s1[i]== '(')
s.push(s1[i++]);
else if(s1[i]== 'S')
{
s.push(s1[i]);
i=i+ 4;
}
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]== '/'||s1[i]== 'S')
{
while(pro(s.top())>=pro(s1[i]))
{
s2+=s.top();
s2+= ' ';
s.pop();
}
s.push(s1[i]);
i++;
}
else if(s1[i]<= '9'&&s1[i]>= '0'||s1[i]== '.')
{
while(s1[i]<= '9'&&s1[i]>= '0'||s1[i]== '.')
s2+=s1[i++];
s2+= ' ';
}
else if(s1[i]== ','||s1[i]== 'x')
i++;
}
while(s.top()!= '#')
{
s2+=s.top();
s.pop();
s2+= ' ';
}
//cout<<s2<<endl;
}
double countt()
{
int len=s2.length(),i= 0;
double y,x;
while(i<len)
{
if(s2[i]== ' ')
i++;
else
{
switch(s2[i])
{
case '+':
x=c.top();
c.pop();
x+=c.top();
c.pop();
i++;
break;
case '*':
x=c.top();
c.pop();
x*=c.top();
c.pop();
i++;
break;
case 'S':
{
int a=c.top();
c.pop();
int b=c.top();
c.pop();
int c,da = 0,db = 0;
while(b!= 0)
{
db += b% 10;
b /= 10;
}
while(a!= 0)
{
da += a% 10;
a /= 10;
}
x = max(da,db);
i++;
break;
}
default :
{
x= 0. 0;
while(s2[i]<= '9'&&s2[i]>= '0')
x=x* 10+(s2[i++]- '0');
}
}
c.push(x);
}
}
return c.top();
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>s1;
s2= "";
deal();
printf( "%.0lf\n",countt());
}
return 0;
}
代碼2：
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
using namespace std;
stack< char> s1;
stack< int> s2;
char s[ 1010];
int main()
{
int T;
scanf( "%d",&T);
while(T--)
{
int i,j;
getchar();
scanf( "%s",&s[ 1]);
int len = strlen(&s[ 1]);
s[ 0] = '(';
s[len+ 1] = ')';
len++;
for(i= 0;i<=len;i++)
{
if(s[i]== '(')
{
s1.push(s[i]);
}
else if(s[i]== 'S')
{
s1.push( '(');
s1.push( 'S');
i += 4;
}
else if(s[i]>= '0' && s[i]<= '9')
{
int v = 0;
while(s[i]>= '0' && s[i]<= '9')
{
v = v* 10+(s[i++]- '0');
}
i--;
s2.push(v);
}
else if(s[i]== '+' || s[i]== '-')
{
while(s1.top()!= '(' && s1.top()!= 'S')
{
int a = s2.top(); s2.pop();
int b = s2.top(); s2.pop();
int c;
switch(s1.top())
{
case '+': c = b + a; break;
case '-': c = b - a; break;
case '*': c = b * a; break;
case '/': c = b / a; break;
}
s2.push(c);
s1.pop();
}
s1.push(s[i]);
}
else if(s[i]== '*' || s[i]== '/')
{
if(s1.top()== '*' )
{
int a = s2.top(); s2.pop();
int b = s2.top(); s2.pop();
s2.push(b*a);
s1.pop();
}
else if(s1.top()== '/')
{
int a = s2.top();s2.pop();
int b = s2.top();s2.pop();
s2.push(b/a);
s1.pop();
}
s1.push(s[i]);
}
else if(s[i]== ')')
{
while(s1.top()!= '(' && s1.top()!= 'S')
{
int a = s2.top();s2.pop();
int b = s2.top();s2.pop();
int c,da = 0 ,db = 0;
switch(s1.top())
{
case '+': c = b + a; break;
case '-': c = b - a; break;
case '*': c = b * a; break;
case '/': c = b / a; break;
}
s2.push(c);
s1.pop();
}
if(s1.top()== 'S')
{
int a=s2.top();s2.pop();
int b=s2.top();s2.pop();
int c,da = 0 ,db = 0;
while(b!= 0)
{
db += b% 10;
b /= 10;
}
while(a!= 0)
{
da += a% 10;
a /= 10;
}
c = max(da,db);
s2.push(c);
s1.pop();
}
s1.pop();
}
}
printf( "%d\n",s2.top());
s2.pop();
}
return 0;
}