題目連結: https://zerojudge.tw/ShowProblem?problemid=a017
# 解題思路
用 stack 輔助，做後序走訪吧！！(我超怕 apcs 出這題的啦！！)
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
stack<char> Sy; | |
stack<long long> Num; | |
int comput() | |
{ | |
if(Num.size()<2||Sy.size()<1||Sy.top()=='(') return -1; | |
long long b=Num.top(),a; | |
Num.pop(); | |
a=Num.top(); | |
Num.pop(); | |
char ch=Sy.top(); | |
Sy.pop(); | |
switch(ch) | |
{ | |
case '+': | |
Num.push(a+b); | |
break; | |
case '-': | |
Num.push(a-b); | |
break; | |
case '*': | |
Num.push(a*b); | |
break; | |
case '/': | |
Num.push(a/b); | |
break; | |
case '%': | |
Num.push(a%b); | |
break; | |
} | |
} | |
long long strToint(string &s,int &i) | |
{ | |
while(s[i]<'0'||s[i]>'9') i++; | |
long long re=0; | |
while(s[i]>='0'&&s[i]<='9') | |
re=(re*10+s[i++]-'0'); | |
return re; | |
} | |
int Priority(char ch) | |
{ | |
if(ch=='+'||ch=='-') | |
return 1; | |
else if(ch=='*'||ch=='/'||ch=='%') | |
return 2; | |
else | |
return 0; | |
} | |
int main(){ | |
string s; | |
while(getline(cin,s)){ | |
while(!Sy.empty()) //clean | |
Sy.pop(); | |
while(!Num.empty()) //clean | |
Num.pop(); | |
if(s.empty()) //nothing | |
break; | |
for(int i=0;i<s.length();) | |
{ | |
if(s[i]=='(') | |
{ | |
Sy.push('('); | |
i++; | |
} | |
else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%') | |
if(!Sy.empty()&&Priority(Sy.top())>=Priority(s[i])) | |
{ | |
while(comput()!=-1); | |
Sy.push(s[i++]); | |
} | |
else | |
Sy.push(s[i++]); | |
else if(s[i]==')') | |
{ | |
i++; | |
while(comput()!=-1); | |
if(!Sy.empty()&&Sy.top()=='(') | |
Sy.pop(); | |
} | |
else if(s[i]==' ') | |
i++; | |
else | |
Num.push(strToint(s,i)); | |
} | |
while(comput()!=-1); | |
cout<<Num.top()<<'\n'; | |
} | |
return 0; | |
} |
