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
| #include <cstdio>
#include <cstring>
#include <stack>
#define N 105
char s[N];int len;
struct type {
int tp,data;
} arr[N],tmp[N];int sz=0,tpsz=0;
int code(char c) {
switch(c) {
case '+':
return 0;
case '-':
return 0;
case '*':
return 1;
case '/':
return 1;
case '^':
return 2;
default:
return -1;
}
}
bool cmp(char a,char b) {
if(a=='^'&&b=='^') return false;
return code(a)>=code(b);
}
int qpow(int n,int k) {
int ans=1;
while(k) {
if(k&1) ans*=n;
n=n*n;k>>=1;
}
return ans;
}
inline void print() {
for(register int i=0;i<sz;++i) {
if(arr[i].tp) printf("%c",(char)arr[i].data);
else printf("%d",arr[i].data);
putchar(i+1<sz?' ':'\n');
}
}
int main() {
scanf("%s",s);len=strlen(s);
std::stack<char> op;
for(register int i=0;i<len;++i) {
if('0'<=s[i]&&s[i]<='9') {
arr[sz++]=(type){0,s[i]-'0'};
}
else if(s[i]=='(') {
op.push(s[i]);
}
else if(s[i]==')') {
while(op.top()!='(') {
arr[sz++]=(type){1,op.top()};op.pop();
}
op.pop();
}
else {
while(!op.empty()&&cmp(op.top(),s[i])) {
arr[sz++]=(type){1,op.top()};
op.pop();
}
op.push(s[i]);
}
}
while(!op.empty()) {
int cur=op.top();
if(cur!='(') arr[sz++]=(type){1,cur};op.pop();
}
print();
while(sz>1) {
bool find=false;tpsz=0;
for(register int i=0;i<sz;++i) {
if(!find&&arr[i].tp) {
find=true;
int y=tmp[--tpsz].data;
int x=tmp[--tpsz].data;
switch(arr[i].data) {
case '+':
tmp[tpsz++]=(type){0,x+y};
break;
case '-':
tmp[tpsz++]=(type){0,x-y};
break;
case '*':
tmp[tpsz++]=(type){0,x*y};
break;
case '/':
tmp[tpsz++]=(type){0,x/y};
break;
case '^':
tmp[tpsz++]=(type){0,qpow(x,y)};
break;
default:
break;
}
}
else tmp[tpsz++]=arr[i];
}
for(register int i=0;i<tpsz;++i) arr[i]=tmp[i];sz=tpsz;
print();
}
return 0;
}
|