Evaluating the mathmatic expression with parentheses

Problem

Given arithmetic equation, 2+(3-1)*4/(5-6), write the program to calculate the result of the equation.

This question is similar to the "Evaluating arithmetic equation", but it is more complicate due to the parentheses.

This problem can be solved using Dijkstra's Shunting-yard algorithm to turn the infix mathematic expression to "Reverse Polish notation", which can be calculated easily.

Conversion of original equation into "Reverse Polish notation", $O(N)$

Using the Dijstra's Shunting-yard algorithm, we first need to convert "infix" mathematic equations into "Reverse Polish notations", which can be easily evaluated. (See Figure 1. for the algorithm explanation.)

Figure 1. Graphical illustration of algorithm

Basically, this algorithm keeps one output queue and one stack for the operators.

1. Scan the expression from left to right.

1-1 if  current value is number
      add the value to output queue.

1-2. if current value is arithmetic operator (e.g. +,/,-, *, ^)

      a) if there is any arithmetic operators which priority is greater or equal to the current value.
           pop the operators from the stack and enqueue them into the output queue. (Step D in Figure 1)
      b) push the current value to the stack

1-3) if current value is left parentheses, "("  
         push the parentheses to the stack

1-4) if the current value is right parentheses

         pop all the operators until left parentheses is encountered and put them into the queue.
         pop left parentheses from the stack
2. pop the operators from the stack and put them into the queue.

3. return the queue

This algorithm produce the Reverse polish notations, which can be parsed in the next step.

Evaluate Reverse Polish notations, $O(N)$

We can now evaluate the math expression using the same algorithm in "Evaluating reverse polish notations".

This algorithm is fairly simple to understand and implement.

1. Scan the expression from left to right.

1-1 if the token is number, push it into a stack

1-2 if the token is a operator, pop two numbers from the stack and compute the result.

    push the result into the stack

2. return the final result in the stack.

Running time of this algorithm is $O(N)$, where the N is # of tokens.

Here is the complete code.

	#include<map>
	#include<list>
	#include<vector>
	#include<string>
	#include<math.h>
	#include<iostream>
	using namespace std;
	bool is_num(char c)
	{
	return c>='0' && c<='9';
	}
	bool is_op(char c)
	{
	return c == '+' || c == '-' || c == '/' || c == '*' || c == '^';
	}
	vector<string> convert_to_polish(string& input)
	{
	vector<string> queue;
	list<string> stack;
	map<char, int> op_order;
	op_order['+'] = 4;
	op_order['-'] = 4;
	op_order['*'] = 3;
	op_order['/'] = 3;
	op_order['^'] = 2;
	string num;
	for (int i = 0; i < input.length(); i++)
	{
	char c = input[i];
	if (is_num(c))
	{
	num.push_back(c);
	} else
	{
	if (num.length())
	{
	queue.push_back(num);
	num = "";
	}
	if (is_op(c))
	{
	string op(1, c);
	while(stack.size())
	{
	string prev = stack.back();
	if(!is_op(prev[0]) || op_order[prev[0]] > op_order[c])
	break;
	queue.push_back(prev);
	stack.pop_back();
	}
	stack.push_back(op);
	} else if ( c == '(')
	{
	string p;
	p.push_back(c);
	stack.push_back(p);
	} else if (c == ')')
	{
	while(stack.size())
	{
	string prev = stack.back();
	if(prev == "(")
	break;
	queue.push_back(prev);
	stack.pop_back();
	}
	stack.pop_back();
	}
	}
	if (i == input.length()-1 && num.length())
	queue.push_back(num);
	}
	while(stack.size())
	{
	string op = stack.back();
	stack.pop_back();
	queue.push_back(op);
	}
	return queue;
	}
	double compute(double l, double r, char op)
	{
	if (op == '+')
	return l+r;
	if (op == '-')
	return l-r;
	if (op == '*')
	return l*r;
	if (op == '/')
	return l/r;
	if (op == '^')
	return pow(l, r);
	return INT_MIN;
	}
	double evaluate(string& input)
	{
	vector<string> parsed = convert_to_polish(input);
	vector<double> num;
	for(int i =0; i < parsed.size(); i++)
	{
	if (parsed[i].length()==1 && is_op(parsed[i][0]))
	{
	double r = num.back();
	num.pop_back();
	double l = num.back();
	num.pop_back();
	double result = compute(l, r, parsed[i][0]);
	if (result == INT_MIN)
	{
	cout<<"invalid operation. "<<endl;
	return INT_MIN;
	}
	num.push_back(result);
	} else {
	num.push_back(stod(parsed[i], 0));
	}
	}
	return (num.size())? num[0]: INT_MIN;
	}
	int main()
	{
	string input ="(3+4)*6+3^2-4";
	cout<< input<<" = "<< evaluate(input)<<endl;
	string input2 ="3+4*6+3^2-4";
	cout<< input2<<" = "<< evaluate(input2)<<endl;
	return 1;
	}

view raw parse_math_expression_with_parentheses.cpp hosted with ❤ by GitHub

Here is another way to parse the expression by examining from the right to left. 

This way does not use Reverse Polish notations. It is a bit more complicated but if you don't remember the reverse polish notation algorithm, you can use it.

	class ComputeExpression:
	def is_number(self, number):
	return number.isdigit()
	def is_op(self, oprand):
	return oprand == '+' or oprand == '-' or oprand == '/' or oprand =='*' or oprand == ')' or oprand == '('
	def is_left_parenthesis(self, oprand):
	return oprand == '('
	def is_plus_minus(self, oprand):
	return oprand == '+' or oprand == '-'
	def is_multiple_or_divide(self, oprand):
	return oprand == '/' or oprand == '*'
	def parse(self, expression):
	self.op = []
	self.numbers = []
	pos = len(expression) -1
	number = ''
	while pos >= 0:
	next = expression[pos]
	if self.is_number(next) is True:
	number = next + number
	elif self.is_op(next) is True:
	if len(number) > 0:
	self.numbers.append(int(number))
	number = ''
	self.handle_op(next)
	pos -= 1
	if len(number) > 0 :
	self.numbers.append(int(number))
	while(len(self.op) > 0):
	next_op = self.op.pop()
	lvalue = self.numbers.pop()
	rvalue = self.numbers.pop()
	result = self.compute(next_op, lvalue, rvalue)
	self.numbers.append(result)
	return self.numbers[0]
	def handle_op(self, cur_op):
	if self.is_left_parenthesis(cur_op) is True:
	self.compute_in_parenthesis()
	return
	if self.is_plus_minus(cur_op) is True and len(self.op) > 0 and self.is_multiple_or_divide(self.op[-1]) is True:
	#compute previous plus and minue ops first before adding current multiple/divide op
	while len(self.op) > 0:
	cur = self.op[-1]
	if self.is_multiple_or_divide(cur) != True:
	break
	lvalue = self.numbers.pop()
	rvalue = self.numbers.pop()
	result = self.compute(cur, lvalue, rvalue)
	self.numbers.append(result)
	self.op.pop()
	self.op.append(cur_op)
	def compute_in_parenthesis(self):
	#compute all ops until right ')'
	while len(self.op) > 0:
	cur = self.op[-1]
	if cur == ')':
	self.op.pop()
	break
	lvalue = self.numbers.pop()
	rvalue = self.numbers.pop()
	result = self.compute(cur, lvalue, rvalue)
	self.numbers.append(result)
	self.op.pop()
	def compute(self, oprand, lvalue, rvalue):
	if (oprand == '+'):
	return lvalue + rvalue
	elif (oprand == '-'):
	return lvalue - rvalue
	elif (oprand == '*'):
	return lvalue * rvalue
	elif (oprand == '/'):
	return lvalue / rvalue
	return None
	c = ComputeExpression()
	expr ="2+(3-1)*4/(5-6)"
	print("%s = %d" % (expr, c.parse(expr)))
	expr ="24+3*14-2"
	print("%s = %d" % (expr, c.parse(expr)))
	expr ="2+(3-1*1-2)*4/(5-6)"
	print("%s = %d" % (expr, c.parse(expr)))

view raw parse_alrithmatic_expr.py hosted with ❤ by GitHub

This is the reverse polish notation solution in python

	from collections import deque
	class ComputeExpression():
	op_rank = {'*': 1, '/':1, '+': 0, '-': 0}
	def parse(self, expr):
	queue = self.reverse_polish(expr)
	stack = []
	print(queue)
	for i in list(queue):
	if self.is_num(i):
	stack.append(int(i))
	elif self.is_op(i):
	rvalue = stack.pop()
	lvalue = stack.pop()
	result = self.compute(i, lvalue, rvalue)
	stack.append(result)
	return stack[0]
	def reverse_polish(self, expr):
	queue = deque()
	num = ''
	op_stack = []
	for i in expr:
	if self.is_num(i):
	num = num + i
	else:
	if len(num) > 0:
	queue.append(num)
	num = ''
	if self.is_op(i):
	pos = len(op_stack) -1
	while pos >= 0:
	cur = op_stack[pos]
	if self.is_op(cur) != True or self.rank(i) > self.rank(cur):
	break
	queue.append(op_stack.pop())
	pos -= 1
	op_stack.append(i)
	elif i == '(':
	op_stack.append(i)
	elif i == ')':
	pos = len(op_stack) -1
	while pos >= 0:
	cur = op_stack[pos]
	if cur == "(":
	op_stack.pop()
	break
	queue.append(op_stack.pop())
	pos -= 1
	if len(num) > 0:
	queue.append(num)
	#put everything in op_stack into queue
	while len(op_stack) > 0:
	queue.append(op_stack.pop())
	return queue
	def compute(self, oprand, lvalue, rvalue):
	if (oprand == '+'):
	return lvalue + rvalue
	elif (oprand == '-'):
	return lvalue - rvalue
	elif (oprand == '*'):
	return lvalue * rvalue
	elif (oprand == '/'):
	return lvalue / rvalue
	return None
	def is_num(self, number):
	return number.isdigit()
	def is_op(self, oprand):
	return oprand == '+' or oprand == '-' or oprand == '/' or oprand =='*'
	def rank(self, op):
	return self.op_rank[op]
	c = ComputeExpression()
	expr ="2+(3-1)*4/(5-6)"
	print("%s = %d" % (expr, c.parse(expr)))
	expr ="24+3*14-2"
	print("%s = %d" % (expr, c.parse(expr)))
	expr ="2+(3-1*1-2)*4/(5-6)"
	print("%s = %d" % (expr, c.parse(expr)))

view raw parse_alrithmatic_expr_reverse_polish.py hosted with ❤ by GitHub

UPDATE: 03/31/2022

Solve the question again using Dijkstra's shunting-yarn algorithm. Did not use the python deque. Instead, use the list with pop(0). (in practice, pop(0) takes a $O(N)$ time.  It is easier to understand.

	op_order = {'*': 1, '/': 1, '+': 2, '-': 2}
	def is_operand(input):
	return input == '+' or input == '-' or input =='*' or input == '/'
	def is_non_number(input):
	return input == '(' or input == ')' or is_operand(input)
	def compute(left, right, op):
	if op == '+':
	return left + right
	elif op == '-':
	return left - right
	elif op == '*':
	return left * right
	elif op == '/':
	return left / right
	def convert_to_polish(expr):
	queue = []
	op_stack = []
	prev = None
	for i in range(len(expr)):
	cur = expr[i]
	if is_non_number(cur) == True:
	# empty the prev if not empty
	if prev is not None:
	queue.append(int(prev))
	prev = None
	if cur == '(':
	op_stack.append(cur)
	elif cur == ')':
	# pop all pos in the stack until '(' and add to the queue
	while len(op_stack) > 0:
	op = op_stack.pop()
	if op == '(':
	break
	queue.append(op)
	elif is_operand(cur) == True:
	# pop all Ops lower or equal to the current one.
	while len(op_stack) > 0 and op_stack[-1] != '(' and op_order[cur] >= op_order[op_stack[-1]]:
	op = op_stack.pop()
	queue.append(op)
	op_stack.append(cur)
	else: # number
	prev = prev + cur if prev is not None else cur
	if prev is not None:
	queue.append(int(prev))
	# empty the rest of operand
	while len(op_stack) > 0:
	queue.append(op_stack.pop())
	return queue
	def calculate(input):
	queue = convert_to_polish(input)
	print(queue)
	num_stack = []
	# now start computing
	while len(queue) > 0:
	cur = queue.pop(0)
	if is_operand(cur) != True:
	num_stack.append(cur)
	else:
	right = num_stack.pop()
	left = num_stack.pop()
	result = compute(left, right, cur)
	num_stack.append(result)
	return num_stack.pop() if len(num_stack) == 1 else None
	input = ['1*(4+1)' ,'2+(3+3)-4*2+12/3', '3+4/2*(3+2)', '100/2+(50-10)/2+1000']
	expected= [5,4, 13, 1070]
	actual = []
	for i in input:
	output =calculate(i)
	actual.append(output)
	print("expected = {}, actual={}".format(expected, actual))

view raw amazon_math_expression_with_paranthesis.py hosted with ❤ by GitHub

Coding: 37 mins

Debugging: 15 mins (had a bug but could not find it quickly)