f377 - 運算式轉換
題目描述
題目要求將一個中序運算式轉換為後序運算式。中序運算式是我們日常書寫的表達式形式，例如 a+b*c。後序運算式，也稱為波蘭式，將運算符放在操作數之後，例如 a b c * +。題目給定的中序運算式包含加、減、乘、除和括號，需要按照運算符的優先級和括號的規則進行轉換。
解題思路
本題使用堆疊 (Stack) 資料結構來實現中序轉後序的演算法。演算法的步驟如下：
- 遍歷中序運算式中的每個字元。
- 如果字元是操作數（字母），則直接輸出。
- 如果字元是左括號
(，則將其壓入堆疊。 - 如果字元是右括號
)，則從堆疊中彈出運算符，直到遇到左括號為止，並輸出彈出的運算符。然後將左括號彈出（但不輸出）。 - 如果字元是運算符（
+,-,*,/），則將其與堆疊頂部的運算符的優先級進行比較。如果堆疊頂部的運算符優先級更高或相等，則從堆疊中彈出運算符並輸出，直到堆疊頂部的運算符優先級低於當前運算符或堆疊為空。然後將當前運算符壓入堆疊。 - 遍歷完中序運算式後，將堆疊中剩餘的所有運算符彈出並輸出。
p() 函數用於定義運算符的優先級。括號的優先級最高，乘除的優先級高於加減。
複雜度分析
- 時間複雜度: O(n)，其中 n 是中序運算式的長度。因為每個字元最多被壓入和彈出堆疊一次。
- 空間複雜度: O(n)，在最壞的情況下，例如
((((a+b))))，堆疊可能需要儲存所有左括號和運算符。
程式碼
#include <iostream>
#include <stack>
using namespace std;
inline int p(char x){
if(x=='+'||x=='-'){
return 1;
}
else if(x=='*'||x=='/'){
return 2;
}
else{
return 0;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string input;
while(getline(cin,input)){
stack <char> back;
for(int i=0,il=input.length();i<il;++i){
if(input[i]!=' '){
if(input[i]=='('){
back.push('(');
}
else if(input[i]=='+'||input[i]=='-'||input[i]=='*'||input[i]=='/'){
while(!back.empty()&&p(back.top())>=p(input[i])){
cout << back.top() << " ";
back.pop();
}
back.push(input[i]);
}
else if(input[i]==')'){
while(!back.empty()&&back.top()!='('){
if(back.top()!='('&&back.top()!=')')cout << back.top() << " ";
back.pop();
}
back.pop();
}
else{
cout << input[i] << " ";
}
}
}
while(!back.empty()){
if(back.top()!='('&&back.top()!=')')cout << back.top() << " ";
back.pop();
}
cout << "\n";
}
}