一般我們常看到的運算式，像是 a + b * c 或 a / b – c 都是中序運算式 (Infix Notation)，可是電腦不懂得如何處理中序運算式，所以電腦會先把中序運算式轉成後序運算式 (Postfix Notation)或前序運算式 (Prefix Notation) 再計算。現在你的任務是寫一個程式模擬中序運算式轉換成後序運算式。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| EOF 輸入 每筆測資一行 每一行會有一個中序運算式，每個運算子及運算元都會以空格分隔 運算元有6種 ‘+’、’-‘、’*’、’/’、'(‘、’)’ 分別代表加減乘除與括號 優先順序: 括號 > 乘除 > 加減 運算子是小寫的英文字母 | 請你輸出順序由左到右轉換好的後序運算式 每個運算子及運算元以空格分隔 |
| a + b * c a / b – c a + b * ( c * ( d + e ) ) | a b c * + a b / c – a b c d e + * * + |
解題思路
一個一個字元判斷，如果讀到字母就直接將其輸出。
宣告一個 stack，用來存運算元。當讀到一個運算元時和 stack 中的資料做比較，如果 stack 裡面沒有東西就將目前的運算元 push 到 stack 中。反之，要先判斷運算元是否是右括號「)」，如果是右括號，將 stack 中的資料從上到下依序輸出，直到遇到左括號「)」，不用輸出左括號但是要 pop 掉它。如果是其他的運算元則判斷目前運算元的優先度是否 <= stack.top() 的優先度，如果是的話就將 stack 中的資料從上到下依序輸出，但是遇到比目前這個運算元優先度還要高的運算元就要停下，或是遇到左括號也要停下。如果不是右括號最後都要將運算元 push 到 stack 中。所有運算子和運算元都判斷完之後就將 stack 中的「所有資料」從上到下輸出。
範例程式碼－ZeroJudge f377: 運算式轉換
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
unordered_map<char, int>MAP;
MAP['*'] = 1;
MAP['/'] = 1;
MAP['('] = 2;
MAP[')'] = 2;
string str;
while (getline(cin, str)) {
stack<char> st;
for (int i = 0; i<str.length(); i++) {
const char ch = str[i];
if (ch == ' ') continue;
if (isalpha(ch)) cout << ch << " ";
else {
if (st.empty()) st.push(str[i]);
else {
if (ch == ')') {
while (!st.empty()) {
if (st.top() == '(') {
st.pop();
break;
}
cout << st.top() << " ";
st.pop();
}
}
else {
if (MAP[ch] <= MAP[st.top()]) {
while (!st.empty() && MAP[ch] <= MAP[st.top()]) {
if (st.top() == '(') {
break;
}
cout << st.top() << " ";
st.pop();
}
}
st.push(ch);
}
}
}
}
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
cout << "\n";
}
}
//ZeroJudge F377
//Dr. SeanXD