Rewrite an ordinary expression in postfix, where each operator comes after its operands.
What to build
A converter from infix to postfix that uses a stack of operators.
Requirements
- Operands are single lowercase letters, and the operators are
+,-,*and/. *and/are done before+and-. Operators of equal precedence are done from left to right.- Round brackets may change the order.
- Print the postfix form with no spaces.
Input
One line with a valid expression of 1 to 100 characters, with no spaces.
Output
The postfix form on one line.
Constraints
The expression has only lowercase letters, the four operators and round brackets.
Example
Input:
a+b*c
Output:
abc*+
Why it works
An operator has to wait until its right operand has been written. The stack holds the waiting operators, and precedence decides which of them must be written before a new one is pushed.
Examples
a+b*c
abc*+
(a+b)*c
ab+c*
Hints
Hint 1
A letter goes straight to the output.
Hint 2
Before pushing an operator, pop and print every operator on top of the stack whose precedence is higher or equal. An opening bracket stops the popping.
Hint 3
A closing bracket pops and prints down to the opening bracket, which is thrown away. At the end, pop everything.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int prec(char op) {
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0; /* an opening bracket */
}
int main(void) {
char expr[101], st[101];
int top = -1;
scanf("%100s", expr);
for (int i = 0; expr[i] != '\0'; i++) {
char c = expr[i];
if (c >= 'a' && c <= 'z') {
printf("%c", c);
} else if (c == '(') {
st[++top] = c;
} else if (c == ')') {
while (st[top] != '(') printf("%c", st[top--]);
top--;
} else {
while (top >= 0 && prec(st[top]) >= prec(c)) printf("%c", st[top--]);
st[++top] = c;
}
}
while (top >= 0) printf("%c", st[top--]);
printf("\n");
return 0;
}