a017 - 五則運算
題目描述
題目要求計算包含加、減、乘、除、餘和括號的五則運算式結果。輸入為包含運算元和運算子的字串，運算元和運算子以空格分隔。需要考慮運算優先順序（先乘除後加減）和括號優先順序。
解題思路
程式碼使用堆疊 (stack) 來實現運算式的計算。主要思路是將中序表示式轉換為後置表示式（postfix notation），然後再計算後置表示式的值。
- 字串解析： 程式碼逐個字符地讀取輸入字串。
- 堆疊操作：
- 如果遇到運算元，則將其添加到後置表示式字串
c中。 - 如果遇到左括號
(，則將其壓入堆疊d中。 - 如果遇到右括號
)，則從堆疊中彈出運算子，直到遇到左括號為止，並將彈出的運算子添加到後置表示式字串c中。然後將左括號彈出。 - 如果遇到運算子，則根據運算子的優先順序，將堆疊中優先順序更高的運算子彈出到後置表示式字串
c中，然後將當前運算子壓入堆疊d中。
- 如果遇到運算元，則將其添加到後置表示式字串
- 後置表示式計算： 程式碼將後置表示式字串
c轉換為數字和運算子的序列，並使用另一個堆疊s來計算結果。- 如果遇到運算元，則將其轉換為整數並壓入堆疊
s中。 - 如果遇到運算子，則從堆疊
s中彈出兩個運算元，執行運算，然後將結果壓入堆疊s中。
- 如果遇到運算元，則將其轉換為整數並壓入堆疊
- 輸出結果： 最後，堆疊
s中只剩一個值，即為運算式的值。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是輸入字串的長度。最壞情況下，需要遍歷字串兩次（一次解析，一次計算），並且堆疊操作可能需要遍歷堆疊中的所有元素。
- 空間複雜度: O(n)，其中 n 是輸入字串的長度。堆疊
d和s的最大大小取決於輸入字串的長度。後置表示式字串c的大小也取決於輸入字串的長度。
程式碼
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(){
string a,c;
stack<char> d;
stack<int> s;
int i=0,x=0;
while(getline(cin,a)){
for(i=0,c.clear();i<a.length();i++){
if(a[i]=='(')
d.push('(');
else if((a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='%')){
if(d.empty()==0){
while((d.top()=='*'||d.top()=='/'||d.top()=='%')||((d.top()=='+'||d.top()=='-')&&(a[i]=='+'||a[i]=='-'))){
c+=d.top();
d.pop();
if(d.empty()==1)
break;
}
}
d.push(a[i]);
}
else if(a[i]==')'){
while ( d.top() != '(' ) {
c+=d.top();
d.pop();
}
d.pop();
}
else
c+=a[i];
}
while(d.empty()==0){
c+=d.top();
d.pop();
c+=' ';
}
a.clear();
for(i=0;i<c.length();i++){
while(c[i]<='9'&&c[i]>='0'){
a+=c[i];
i++;
}
x=0;
while(a.length()>0){
for(int i=0;i<a.length();i++){
x+=a[i]-48;
x*=10;
}
x/=10;
s.push(x);
a.clear();
}
x=0;
if(c[i]=='+'){
x=s.top();
s.pop();
s.top()+=x;
}
else if(c[i]=='-'){
x-=s.top();
s.pop();
s.top()+=x;
}
else if(c[i]=='*'){
x+=s.top();
s.pop();
s.top()*=x;
}
else if(c[i]=='/'){
x+=s.top();
s.pop();
s.top()/=x;
}
else if(c[i]=='%'){
x+=s.top();
s.pop();
s.top()%=x;
}
}
cout << s.top() << endl;
}
}