Evaluate Reverse Polish Notation

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
AppleOracleLinkedIn

Problem statement

You are given an arithmetic expression in Reverse Polish Notation in the form of an array ‘EXP’. Your task is to evaluate the value of the given expression. Since the final value can be large, output it Modulo 10^9+7.

Reverse Polish Notation is a mathematical notation in which the operator appears in the expression after the operands.

For Example:

You are given ‘EXP’ = {‘2’,’3’,’1’,’*’,’+’,’9’,’-’}. Then the result will be -4.
2 3 1 * + 9 -

- : ( ) - ( )
9 : ( ) - (9)
+ : ( ( ) + ( ) ) - (9)
'*':  ( ( ) + ( ( ) * ( ) ) ) - (9)
1 : ( ( ) + ( ( ) * (1) ) ) - (9)
3 : ( ( ) + ( (3) * (1) ) ) - (9)
2 : ( (2) + ( (3) * (1) ) ) - (9) 

Result = (2 + 3) - 9 = 5 - 9 = -4
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer ‘N’, representing the size array ‘EXP’.

The second line of each test case contains ‘N’ space-separated tokens(operators and operands) of the given expression.
Output Format: 
For each test case, print an integer obtained by evaluating the given expression.

Print the output of each test case in a separate line.
Note: 
Operators will only include the basic arithmetic operators like '*', '/', '+', and '-'.

The operand can contain multiple digits.

The operators and operands will have space as a separator between them.

There won’t be any brackets in the given expression.

The answer could be very large, output your answer modulo (10^9+7). Also, use modular division when required.

You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 5000
1 <= NUM <= 100

Where ‘N’ denotes the length of the given expression, and ‘NUM’ denotes the operand.

Time Limit: 1 sec

Sample Input 1:
2
7
2 3 1 * + 9 -
7
1 2 3 + * 8 -
Sample Output 1:
1000000003
1000000004
Explanation of Sample Input 1:
For the first test case:
2 3 1 * + 9 -

- : ( ) - ( )
9 : ( ) - (9)
+ : ( ( ) + ( ) ) - (9)
'*':  ( ( ) + ( ( ) * ( ) ) ) - (9)
1 : ( ( ) + ( ( ) * (1) ) ) - (9)
3 : ( ( ) + ( (3) * (1) ) ) - (9)
2 : ( (2) + ( (3) * (1) ) ) - (9) 

Result = (2 + 3) - 9 = 5 - 9 = -4%(10^9+7) = 1000000003.

For the second test case:
1 2 3 + * 8 -

- : ( ) - ( )
8 : ( ) - (8)
* : ( ( ) * ( ) ) - (8)
+ : ( ( ) * ( ( ) + ( ) ) ) - (8)
3 : ( ( ) * ( ( ) + (3) ) ) - (8)
2 : ( ( ) * ( (2) + (3) ) ) - (8)
1 : ( (1) * ( (2) + (3) ) ) - (8)

Result = (1 * 5) - 8 = 5 - 8 = -3%(10^9+7) = 1000000004.
Sample Input 2:
2
9 
100 200 + 2 / 5 * 7 +
3
1 2 +
Sample Output 2:
757
3
Hint

Try using stack.

Approaches (1)
Stack

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.

 

Algorithm :

  • Create a stack to store the operands.
  • Scan the given expression from left to right. For every scanned element do the following.
    • If the element is a number, extract the full number, that is, increment and form a multi-digit number till space is encountered.
    • 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.
    • 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.
Time Complexity

O(N), where ‘N’ is the length of the given expression.
 

Since we are iterating over the given expression of length ‘N’ and so, the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the length of the given expression.

 

Since we are using a stack to store the elements of the given expression and so, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Evaluate Reverse Polish Notation
Full screen
Console