Evaluate a postfix expression made of whole numbers and the operators + - * /. Division truncates toward zero, as C's / does. The expression is always valid and never divides by zero.
For example, 2 3 * 4 + is (2 * 3) + 4, which is 10.
What to build
A postfix calculator that uses a stack of whole numbers.
Requirements
- Push each number.
- For an operator, pop the right operand first and then the left one.
- Push the result, and print the one value left at the end.
Input
The first line has n (1 ≤ n ≤ 100), the number of tokens. The second line has the n tokens, separated by spaces. Each number is between 0 and 1000.
Output
The value of the expression.
Constraints
1 ≤ n ≤ 100, and each number is from 0 to 1000.
Example
Input:
5
2 3 * 4 +
Output:
10
Why it works
In postfix an operator always follows its two operands, so they are the two most recent values, which is what a stack returns.
Examples
5 2 3 * 4 +
10
7 100 20 5 / - 3 *
288
Hints
Hint 1
Read each token with scanf("%15s", tok). An operator is one character: + - * or /.
Hint 2
A number is pushed: atoi(tok) turns the text into an int.
Hint 3
An operator pops b first, then a, and pushes a op b.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int n;
scanf("%d", &n);
int st[100];
int top = -1;
for (int i = 0; i < n; i++) {
char tok[16];
scanf("%15s", tok);
if (tok[0] >= '0' && tok[0] <= '9') {
st[++top] = atoi(tok);
} else {
int b = st[top--];
int a = st[top--];
if (tok[0] == '+') st[++top] = a + b;
else if (tok[0] == '-') st[++top] = a - b;
else if (tok[0] == '*') st[++top] = a * b;
else st[++top] = a / b;
}
}
printf("%d\n", st[top]);
return 0;
}