Typically, the expressions we commonly see, such as a + b * c or a / b - c, are in infix notation. However, computers do not know how to directly process infix notation. Instead, they first convert infix notation into postfix notation or prefix notation before performing calculations. Your task now is to write a program that simulates the conversion of an infix expression into postfix 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