Reverse Polish ‘Notation is postfix notation which in terms of mathematical notion signifies operators following operands. Let’s take a problem statement to implement RPN
Problem Statement: The task is to find the value of the arithmetic expression present in the array using valid operators like +, -, *, /. Each operand may be an integer or another expression.
Note:
- The division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Layman Working of RPN as shown
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Approach:
The basic approach for the problem is using the stack.
- Accessing all elements in the array, if the element is not matching with the special character (‘+’, ‘-‘,’*’, ‘/’) then push the element to the stack.
- Then whenever the special character is found then pop the first two-element from the stack and perform the action and then push the element to stack again.
- Repeat the above two process to all elements in the array
- At last pop the element from the stack and print the Result
Implementation:
C++
#include <bits/stdc++.h>using namespace std;int eval(vector<string>& A){ stack<int> st; for (int i = 0; i < A.size(); i++) { if (A[i] != "+" && A[i] != "-" && A[i] != "/" && A[i] != "*") { st.push(stoi(A[i])); continue; } else { int b = st.top(); st.pop(); int a = st.top(); st.pop(); if (A[i] == "+") st.push(a + b); else if (A[i] == "-") st.push(a - b); else if (A[i] == "*") st.push(a * b); else st.push(a / b); } } return st.top();}int main(){ vector<string> A = { "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" }; int res = eval(A); cout << res << endl;} |
Java
// Java Program to find the// solution of the arithmetic// using the stackimport java.io.*;import java.util.*;class solution { public int stacky(String[] tokens) { // Initialize the stack and the variable Stack<String> stack = new Stack<String>(); int x, y; String result = ""; int get = 0; String choice; int value = 0; String p = ""; // Iterating to the each character // in the array of the string for (int i = 0; i < tokens.length; i++) { // If the character is not the special character // ('+', '-' ,'*' , '/') // then push the character to the stack if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") { stack.push(tokens[i]); continue; } else { // else if the character is the special // character then use the switch method to // perform the action choice = tokens[i]; } // Switch-Case switch (choice) { case "+": // Performing the "+" operation by popping // put the first two character // and then again store back to the stack x = Integer.parseInt(stack.pop()); y = Integer.parseInt(stack.pop()); value = x + y; result = p + value; stack.push(result); break; case "-": // Performing the "-" operation by popping // put the first two character // and then again store back to the stack x = Integer.parseInt(stack.pop()); y = Integer.parseInt(stack.pop()); value = y - x; result = p + value; stack.push(result); break; case "*": // Performing the "*" operation // by popping put the first two character // and then again store back to the stack x = Integer.parseInt(stack.pop()); y = Integer.parseInt(stack.pop()); value = x * y; result = p + value; stack.push(result); break; case "/": // Performing the "/" operation by popping // put the first two character // and then again store back to the stack x = Integer.parseInt(stack.pop()); y = Integer.parseInt(stack.pop()); value = y / x; result = p + value; stack.push(result); break; default: continue; } } // Method to convert the String to integer return Integer.parseInt(stack.pop()); }}class GFG { public static void main(String[] args) { // String Input String[] s = { "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" }; solution str = new solution(); int result = str.stacky(s); System.out.println(result); }} |
Python3
# Python 3 code to evaluate reverse polish notation"""This code is contributed by Harshal Gupta"""# function to evaluate reverse polish notationdef evaluate(expression): # splitting expression at whitespaces expression = expression.split() # stack stack = [] # iterating expression for ele in expression: # ele is a number if ele not in '/*+-': stack.append(int(ele)) # ele is an operator else: # getting operands right = stack.pop() left = stack.pop() # performing operation according to operator if ele == '+': stack.append(left + right) elif ele == '-': stack.append(left - right) elif ele == '*': stack.append(left * right) elif ele == '/': stack.append(int(left / right)) # return final answer. return stack.pop()# input expressionarr = "10 6 9 3 + -11 * / * 17 + 5 +"# calling evaluate()answer = evaluate(arr)# printing final value of the expressionprint(f"Value of given expression'{arr}' = {answer}") |
C#
// C# Program to find the// solution of the arithmetic// using the stackusing System;using System.Collections.Generic;public class GFG { public class Solution { public int stacky(string[] tokens) { // Initialize the stack and the variable Stack<string> stack = new Stack<string>(); int x, y; string result = ""; string choice; int value = 0; string p = ""; // Iterating to the each character // in the array of the string for (int i = 0; i < tokens.Length; i++) { // If the character is not the special // character // ('+', '-' ,'*' , '/') // then push the character to the stack if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") { stack.Push(tokens[i]); continue; } else { // else if the character is the special // character then use the switch method // to perform the action choice = tokens[i]; } // Switch-Case switch (choice) { case "+": // Performing the "+" operation by // popping put the first two character // and then again store back to the // stack x = int.Parse(stack.Pop()); y = int.Parse(stack.Pop()); value = x + y; result = p + value; stack.Push(result); break; case "-": // Performing the "-" operation by // popping put the first two character // and then again store back to the // stack x = int.Parse(stack.Pop()); y = int.Parse(stack.Pop()); value = y - x; result = p + value; stack.Push(result); break; case "*": // Performing the "*" operation // by popping put the first two // character and then again store back // to the stack x = int.Parse(stack.Pop()); y = int.Parse(stack.Pop()); value = x * y; result = p + value; stack.Push(result); break; case "/": // Performing the "/" operation by // popping put the first two character // and then again store back to the // stack x = int.Parse(stack.Pop()); y = int.Parse(stack.Pop()); value = y / x; result = p + value; stack.Push(result); break; default: continue; } } // Method to convert the String to integer return int.Parse(stack.Pop()); } } static public void Main() { // String Input string[] s = { "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" }; Solution str = new Solution(); int result = str.stacky(s); Console.WriteLine( "Value of given expression'10 6 9 3 + -11 * / * 17 + 5 +' = " + result); }}// This code is contributed by lokesh |
Javascript
// Javascript code to evaluate reverse polish notation function eval(A){ // Initialize the stack let st = []; // Iterating to the each character // in the array of the string for (let i = 0; i < A.length; i++) { // If the character is not the special character // ('+', '-' ,'*' , '/') // then push the character to the stack if (A[i] != "+" && A[i] != "-" && A[i] != "/" && A[i] != "*") { st.push(parseInt(A[i])); continue; } // else if the character is the special // character then use them to // perform the action else { let b = parseInt(st.pop()); let a = parseInt(st.pop()); if (A[i] == "+") st.push(a + b); else if (A[i] == "-") st.push(a - b); else if (A[i] == "*") st.push(a * b); else st.push(parseInt(a / b)); } } return parseInt(st[st.length-1]);} let A = [ "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" ]; let res = eval(A); console.log(res); // This code is contributed by Pushpesh Raj. |
Output
Value of given expression'10 6 9 3 + -11 * / * 17 + 5 +' = 22
Time complexity: O(n)
Auxiliary Space: O(n)
Approach – Space Optimized
Follow the below steps to Implement the idea:
- Create two integer variables i = 0 and lastNum (variable for keeping track of the index of the last number seen) = -1.
- Check if the current element is an arithmetic operator (+, -, *, /), If the current element is an arithmetic operator, then do the following:
a. Convert the previous two elements (the operands) to integers and store them in val1(get the second-to-last number seen) and val2(get the last number seen).
b. Perform the operation based on the operator, update the second-to-last number with the result, update the index of the last number seen. - if the current element is a number dp the following:
a.Increment the index of the last number seen.
b.Add the number to the next available index in the array.
Java
import java.util.*;public class Main { public static int eval(String[] tokens) { // initialize a counter for iterating // over the tokens int i = 0; // initialize a variable for keeping track // of the index of the last number seen int lastNum = -1; while (i < tokens.length) { // if the current token is // an operator if ("/*+-".contains(tokens[i])) { // get the second-to-last // number seen int val1 = Integer.valueOf(tokens[lastNum - 1]); // get the last number // seen int val2 = Integer.valueOf(tokens[lastNum]); // initialize a variable for // storing the result of the // operation int ans = 0; // perform the operation based // on the operator if (tokens[i].equals("*")) ans = val1 * val2; else if (tokens[i].equals("/")) ans = val1 / val2; else if (tokens[i].equals("+")) ans = val1 + val2; else if (tokens[i].equals("-")) ans = val1 - val2; // update the second-to-last // number with the result tokens[lastNum - 1] = Integer.toString(ans); // update the index of the last // number seen lastNum--; } // if the current token is a number else { // increment the index of the // last number seen lastNum++; // add the number to the // next available index in // the array tokens[lastNum] = tokens[i]; } i++; // increment the counter for iterating over // the tokens } return Integer.valueOf( tokens[lastNum]); // return the final result } public static void main(String[] args) { String[] tokens = { "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" }; int res = eval(tokens); System.out.println( "Value of given expression '10 6 9 3 + -11 * / * 17 + 5 +' = " + res); }}// this code is contributed by Ravi Singh |
Output
Value of given expression '10 6 9 3 + -11 * / * 17 + 5 +' = 22
Time Complexity: O(N)
Space Complexity: O(1)
