Evaluating the reverse polish notation

Problem

Given the list of strings consisting of the asthmatic equation expressed in the Reverse Polish notation.
Write the program that evaluates the equation and returns the result.

Example:
   For {"4","1","+","2.5","*"}, output =12.5
   {"5", "80","40","/","+"} = 7


Answer

This question is similar to a previous question, "Evaluating arithmetic equation" but is simpler because the priority among operator had been handled already.

First of all we first need to understand Reverse Polish notation. (Read this link before proceed).

Based on Reverse polish notation, {"4","1","+","2.5","*"} equals to $(4+1) \times 2.5$ while {"5", "80","40","/","+"} is equivalent to $5+(80/40)$.

We can use the stack to solve this problem. Here is the rough algorithm:

1. Iterate over the list of strings.

2. If the current string is a number, push back the number into the stack

3. If the number is operator, take 2 numbers from the stack and compute the result before pushing back the result into the stack.

4. Return the number left on the top of the stack.

The running time of this algorithm is $O(N)$

Here is the complete code.

	#include <vector>
	#include <string>
	#include <iostream>
	using namespace std;
	double compute(double l, double r, string op)
	{
	if (op =="+")
	return l + r;
	else if (op == "-")
	return l - r;
	else if ( op == "/")
	return l / r;
	else if (op == "*")
	return l*r;
	else
	throw exception("Invalid operand.");
	}
	bool is_op(string op)
	{
	return op == "+"|| op =="-"||op =="/"|| op =="*";
	}
	double eval_polish_expr(string* expr, int len)
	{
	vector<double> nums;
	for (int i = 0; i < len; i++)
	{
	string cur = expr[i];
	if (is_op(cur))
	{
	double r = nums.back();
	nums.pop_back();
	double 1 = nums.back();
	nums.pop_back();
	nums.push_back(compute(l,r, cur));
	} else {
	double n = strtod(cur.c_str(), 0);
	nums.push_back(n);
	}
	}
	return nums[0];
	}
	int main()
	{
	string input[5] = {"4","1","+","2.5","*"};
	string input2[5] = {"5", "80","40","/","+"};
	cout << "input 1 = " << eval_polish_expr(input, 5)<<endl;
	cout << "input 2 = " << eval_polish_expr(input2, 5)<<endl;
	return 1;
	}

view raw eval_polish_expr.cpp hosted with ❤ by GitHub

Practice statistics

19:05: hand-wrote the solution
02:27; validate the solution
21:33: write the code in IDE (3 typos found through compilation)
3:00: fixed the logical flaw after understanding what "Reverse Polish Notation" was



UPDATE (07-17-2019): solved the problem again in python.

Here is the solution in python

	class PolishEquation:
	def solve(self, equation):
	stack = []
	for ch in equation:
	if self.is_operator(ch):
	r = stack.pop()
	l = stack.pop()
	result = self.compute(l, r, ch)
	stack.append(result)
	else:
	stack.append(ch)
	return stack[0]
	def is_operator(self, op):
	return op == '*' or op == '/' or op == '+' or op =='-'
	def compute(self, l, r, op):
	if op == '+':
	return float(l) + float(r)
	elif op == '-':
	return float(l) - float(r)
	elif op == '*':
	return float(l) * float(r)
	elif op == '/':
	return float(l) / float(r)
	raise "invalid operator"
	p = PolishEquation()
	problem = ["4","1","+","2.5","*"]
	print("problem = {} output = {}".format(problem, p.solve(problem)))
	problem = ["5", "80","40","/","+"]
	print("problem = {} output = {}".format(problem, p.solve(problem)))

view raw evaluate_polish_notation.py hosted with ❤ by GitHub

Statistics:

30:00: I think I spent around 20-30 mins with minor typos. Should not happen next time.

UPDATE(2022-06-14): Solved the question again in python

	def is_operand(op):
	return op == '+' or op =='-' or op == '/' or op == '*'
	def compute(left, right, op):
	if op == '+':
	return float(left) + float(right)
	elif op == '-':
	return float(left) + float(right)
	elif op == '/':
	return float(left) / float(right)
	elif op == '*':
	return float(left) * float(right)
	raise("Invaild operand.")
	def evaluate_polish_notation(input): # stack =[12.5] result = 5 i = *
	stack = []
	for i in input:
	if is_operand(i):
	# pop two numbers.
	if len(stack) < 2:
	raise("expression is wrong.")
	right = stack.pop()
	left = stack.pop()
	result = compute(left, right, i)
	stack.append(result)
	else:
	stack.append(i)
	if len(stack) > 1:
	raise("invalid expression")
	return stack[0]
	input = ["4","1","+","2.5","*"]
	result = evaluate_polish_notation(input)
	print("input = {} result = {}".format(input, result))
	input = ["5", "80","40","/","+"]
	result = evaluate_polish_notation(input)
	print("input = {} result = {}".format(input, result))

view raw evaluate_polish_expr.py hosted with ❤ by GitHub

15:17: to write up the code