一般我們常看到的運算式，像是 a + b * c 或 a / b – c 都是中序運算式 (Infix Notation)，可是電腦不懂得如何處理中序運算式，所以電腦會先把中序運算式轉成後序運算式 (Postfix Notation)或前序運算式 (Prefix Notation) 再計算。現在你的任務是寫一個程式模擬中序運算式轉換成後序運算式。
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| •Input format: Input ends with EOF. Each line contains one test case.
•Each test case: Each line contains an infix expression where spaces separate all operators and operands. •Operators: The six operators include +, -, *, /, (, ), representing addition, subtraction, multiplication, division, and parentheses. •Precedence order: Parentheses > Multiplication/Division > Addition/Subtraction. •Operands: Operands are lowercase English letters. | Please output the converted postfix notation from left to right. Each operator and operand should be separated by a space. |
| a + b * c a / b – c a + b * ( c * ( d + e ) ) | a b c * + a b / c – a b c d e + * * + |
Thought Process
Process one character at a time. If a letter is encountered, output it directly.
Declare a stack to store operators. When reading an operator, compare it with the data in the stack:
1. If the stack is empty, push the current operator onto the stack.
2. Otherwise:
•If the operator is a right parenthesis ), output the stack’s contents from top to bottom until encountering a left parenthesis (. Do not output the left parenthesis, but pop it from the stack.
•If the operator is not a right parenthesis, compare its precedence with stack.top(). If its precedence is less than or equal to stack.top(), output the stack’s contents from top to bottom until encountering:
•An operator with a higher precedence than the current operator, or a left parenthesis (.
•After processing, push the current operator onto the stack.
3. After processing all operators and operands, output all remaining data in the stack from top to bottom.
Sample Code－ZeroJudge F377: Arithmetic Conversion
#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