Evaluate Reverse Polish Notation Editorial

Practice Problem Link: Evaluate Reverse Polish Notation

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an arithmetic expression in Reverse Polish Notation (Postfix Notation), evaluate the value. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: a/b should return an integer. It is guaranteed that for any division, the divisor won't be 0.

Approach

The approach to solving this problem is to simulate the operations using a stack. We follow the following steps to simulate the algorithm,

• We iterate over all the elements in the array. If the element is not a special operator ('+', ‘-’, ‘*’, ‘/’) then push it into the stack.
• Whenever a special element is found, we pop the top two elements from the stack and perform the operation. Then we push this result into the stack.
• We repeat the above two steps to process all the elements in the array.
• Finally, pop the element from the stack and return the result.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

int evalRPN(vector<string> &tokens) {
	stack<string> simulateStack;
	string result, choice;
	int value = 0;
	string aux = "";
	for(int i = 0; i < tokens.size(); i++) {
		if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
			simulateStack.push(tokens[i]);
			continue;
		}
		else {
			choice = tokens[i];
		}
		if(choice == "+") {
			int first = stoi(simulateStack.top());
			simulateStack.pop();
			int second = stoi(simulateStack.top());
			simulateStack.pop();
			value = first + second;
			result = aux + to_string(value);
			simulateStack.push(result);
		}
		else if(choice == "-") {
			int first = stoi(simulateStack.top());
			simulateStack.pop();
			int second = stoi(simulateStack.top());
			simulateStack.pop();
			value = second - first;
			result = aux + to_string(value);
			simulateStack.push(result);
		}
		else if(choice == "*") {
			int first = stoi(simulateStack.top());
			simulateStack.pop();
			int second = stoi(simulateStack.top());
			simulateStack.pop();
			value = first * second;
			result = aux + to_string(value);
			simulateStack.push(result);
		}
		else if(choice == "/") {
			int first = stoi(simulateStack.top());
			simulateStack.pop();
			int second = stoi(simulateStack.top());
			simulateStack.pop();
			value = second / first;
			result = aux + to_string(value);
			simulateStack.push(result);
		}
		else {
			continue;
		}
	}
	return stoi(simulateStack.top());
}

Java

class Solution {
	int evalRPN (String[] tokens) {
		Stack<String> stack = new Stack<String>();
		String result, choice;
		int value = 0;
		String aux = "";
		for(int i = 0; i < tokens.length; i++) {
			if(!tokens[i].equals("+") && !tokens[i].equals("-") && !tokens[i].equals("*") && !tokens[i].equals("/")) {
				stack.push(tokens[i]);
				continue;
			}
			else {
				choice = tokens[i];
			}
			if(choice.equals("+")) {
				int first = Integer.parseInt(stack.pop());
				int second = Integer.parseInt(stack.pop());
				value = first + second;
				result = aux + value;
				stack.push(result);
			}
			else if(choice.equals("-")) {
				int first = Integer.parseInt(stack.pop());
				int second = Integer.parseInt(stack.pop());
				value = second - first;
				result = aux + value;
				stack.push(result);
			}
			else if(choice.equals("*")) {
				int first = Integer.parseInt(stack.pop());
				int second = Integer.parseInt(stack.pop());
				value = first * second;
				result = aux + value;
				stack.push(result);
			}
			else if(choice.equals("/")) {
				int first = Integer.parseInt(stack.pop());
				int second = Integer.parseInt(stack.pop());
				value = second / first;
				result = aux + value;
				stack.push(result);
			}
			else {
				continue;
			}
		}
		return Integer.parseInt(stack.pop());
	}
}