Last Updated: 2 Nov, 2020
Evaluation of postfix expression
Easy
Asked in companies
An expression is called the postfix expression if the operator appears in the expression after the operands.
Example :
Infix expression: A + B * C - D
Postfix expression: A B + C D - *
Given a postfix expression, the task is to evaluate the expression. The answer could be very large, output your answer modulo (10^9+7). Also, use modular division when required.
Note:
1. Operators will only include the basic arithmetic operators like '*', '/', '+', and '-'.
2. The operand can contain multiple digits.
3. The operators and operands will have space as a separator between them.
4. There won’t be any brackets in the postfix expression.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The first and only line of each test case contains a postfix expression.
Output format
For each test case, print an integer obtained by evaluating the given postfix expression.
Note:
You are not required to print the expected output; it has already been taken care of, Just implement the function.
Constraints
1 <= T <= 100
1 <= N <= 10^3
1 <= NUM <= 100
Where ‘N’ denotes the length of postfix expression and ‘NUM’ denotes the operand.
Time Limit: 1 sec
Approaches
The idea is to use a stack to store the operands. Whenever an operator is encountered, we pop the top two numbers from the stack, perform the operation and push the result back to the stack. Finally, when the traversal is completed, the number left in the stack is the final answer.
- Create a stack to store the operands.
- Scan the given expression from left to right. For every scanned element do the following.
a. If the element is a number, extract the full number, that is, increment and form a multi-digit number till space is encountered.
b. If the element is an operand, pop the last two operands from the stack. Let the operands are ‘B’ (topmost) and ‘A’ (second from the top) and the operator be ‘*’. Now, evaluate the operator, that is, perform ‘A * B’ (the Second element is taken first, then the operator, and finally the topmost element) and push the result into the stack.
c. If space is encountered, send the control back to the loop using the ‘continue’ statement. - When the expression ends, the number in the stack is the final answer.