Evaluating the mathematic expression without parentheses

Problem

Given the arithmetic expression, $2+3+3-4*2+12/3$, your algorithm should return the result of the calculation.

If we were to calculate the expression from left to right, the problem happens when we encounter, $/, *$. They should be calculated before $+, -$ are evaluated.

One simple way to evaluate from right to left. One advantage of this approach is that you can handle $*, /$ more easily.

Before evaluating the given expression from right to left, you need to have two stacks: one for operands and the other for numbers.

Here is rough algorithm

For $i = n-1 ... 0 $, for each char in the input, $A$

if (current char is number)

   put it into the number buffer

if (current char is $+ or -$)

    for all $* or /$, calculate the result as below:

       pop two numbers from a number stack

       pop one $* or /$ operand from a operand stack

       Compute the result 

       put the result back into the number stack

    put the current char into the operand stack

    if (current char is the first char in $A$)

        put the number int the buffer into the number stack

 for all operands in the operand stack, calculate the result as below:

       pop two numbers from a number stack

       pop one $* or /$ operand from a operand stack

       Compute the result 

       put the result back into the number stack

return the final result

Here is the complete code running in $O(N)$.

	#include <list>
	#include <string>
	#include<iostream>
	using namespace std;
	bool IsNum(char c)
	{
	return (c-'0'>=0 && c -'0' <=9);
	}
	bool IsPlusMinus(char c)
	{
	return (c=='+' || c == '-');
	}
	bool IsMulipleDivide(char c)
	{
	return (c=='*'|| c=='/');
	}
	string calculate(string l, string r, char op)
	{
	int left = stoi(l, 0);
	int right =stoi(r, 0);
	int result;
	if (op == '+')
	result = left+right;
	else if (op =='-')
	result = left - right;
	else if (op == '*')
	result = left*right;
	else if (op == '/')
	result = left/right;
	return to_string(result);
	}
	int eval_expr(string input)
	{
	list<string> nums;
	list<char> ops;
	string cur="";
	for (int i = input.length()-1; i >=0; i--)
	{
	if (IsNum(input[i]))
	{
	cur.insert(0,1, input[i]);
	} else {
	nums.push_back(cur);
	cur ="";
	if (IsPlusMinus(input[i]))
	{
	while(ops.size() && IsMulipleDivide(ops.back()))
	{
	string l = nums.back();
	nums.pop_back();
	string r = nums.back();
	nums.pop_back();
	string result = calculate(l, r, ops.back());
	ops.pop_back();
	nums.push_back(result);
	}
	}
	ops.push_back(input[i]);
	}
	if(i == 0)
	nums.push_back(cur);
	}
	while(ops.size())
	{
	string l = nums.back();
	nums.pop_back();
	string r = nums.back();
	nums.pop_back();
	string result = calculate(l, r, ops.back());
	ops.pop_back();
	nums.push_back(result);
	}
	return stoi(nums.back(),0);
	}
	int main()
	{
	string input = "2+3+3-4*2+12/3";
	cout<<" 2+3+3-4*2+12/3 = " <<eval_expr(input)<<endl;
	return 1;
	}

view raw eval_expr.cpp hosted with ❤ by GitHub

UPDATE(2019-07-26):  solved the problem again using reverse polish notation way. I thought I understood the reverse polish algorithm but I was totally wrong, Started writing the code without clear verification of the reverse polish algorithm. I could not get the right solution even after 1 and 30 minutes. I check how to reverse polish worked and rewrite the code again but took longer than 10 minutes with the bug.

Here is the overall algorithm of using reverse polish notation.

Step 1: Here is how reverse polish works.

- scan the equation from left to right.
    - if current, c is number, add to queue
    - if current c is op:
        - pop all op that is smaller or equal to the current op and add them to the queue
        - add current op to the stack
- for all ops in the stack:
    - pop op and add to the queue

return queue

Step 2: evaluate the reverse polish

for all elements in the reverse polish queue:
    - dequeue an element from the reserse polish queue.
    - if the element is a number add it to the stack.
    - if the element is op:
        - pop number from stack and assign to rvalue
        - pop number from stack and assign to lvalue
        - compute lvalue and rvalue with op and assign to result.
        - add the result to the stack

- pop the final value from the stack (should have only one value)
return the final value.


I wrote the solution in python.

	from collections import deque
	class Expression:
	def convert_to_reverse_polish(self, input):
	op_order = {'+':2, '-':2, '*':1, '/':1, '^':0}
	stack =[]
	queue = deque()
	number = ''
	for c in input:
	if c.isdigit():
	number += c
	elif self.is_op(c):
	if len(number) > 0:
	queue.append(number)
	number = ''
	op = stack[-1] if len(stack) > 0 else None
	while op != None and op_order[c] >= op_order[op]:
	queue.append(op)
	stack.pop()
	op = stack[-1] if len(stack) > 0 else None
	stack.append(c)
	if len(number) > 0:
	queue.append(number)
	while len(stack) > 0:
	queue.append(stack.pop())
	return queue
	def is_op(self, c):
	return c == '*' or c =='+' or c =='/' or c =='-'
	def evaluate(self, input):
	reverse_polish = self.convert_to_reverse_polish(input)
	print reverse_polish
	stack = []
	while len(reverse_polish) > 0:
	current = reverse_polish.popleft()
	if current.isdigit():
	stack.append(current)
	else:
	rvalue = stack.pop()
	lvalue = stack.pop()
	result = self.calculate(lvalue, rvalue, current)
	stack.append(result)
	return stack[0]
	def calculate(self, l, r, op):
	if op == '+':
	return int(l) + int(r)
	elif op == '/':
	return int(l) / int(r)
	elif op == '-':
	return int(l) - int(r)
	elif op == '*':
	return int(l) * int(r)
	e = Expression()
	input='2+3+3-4*2+12/3'
	print("input = {} output ={}".format(input, e.evaluate(input)))

view raw evaluation_equation_reverse_polish.py hosted with ❤ by GitHub

Practice statistics:

12:00 to decide the reverse polish way.

1h:29mins: totally misunderstood the reverse polish algorithm. Initial algorithm validation was wrong and ended up writing wrong code.

UPDATE: 3/30/2022

Write the code with the original two-stack approach with the handling of multi-ditgits.

10 mins: to come up with valid algorithm with minor errors

49 mins: to write up the code and debug the algorithm

Took too long to do it. 

Here

	def is_operand(input):
	return input == '+' or input == '-' or input =='*' or input == '/'
	def is_plusminus(input):
	return input == '+' or input == '-'
	def parse(left, right, op):
	if op == '+':
	return left + right
	elif op == '-':
	return left - right
	elif op == '*':
	return left * right
	elif op == '/':
	return left / right
	def calculate(input):
	operand = []
	numbers = []
	input_length = len(input)
	i = input_length - 1
	prev = None
	while i >= 0:
	cur = input[i]
	if is_operand(cur) != True:
	prev = cur + prev if prev != None else cur
	else:
	if prev is not None:
	numbers.append(int(prev))
	prev = None
	if cur == '*' or cur == '/':
	operand.append(cur)
	elif is_plusminus(cur) :
	# calculate all prior * or /
	while len(operand) > 0 and is_plusminus(operand[-1]) != True:
	right = numbers.pop()
	left = numbers.pop()
	op = operand.pop()
	result = parse(right, left, op)
	numbers.append(result)
	operand.append(cur)
	i = i - 1
	if prev is not None:
	numbers.append(int(prev))
	print("operand ={}, numbers= {}".format(operand, numbers))
	while len(operand) > 0:
	right = numbers.pop()
	left = numbers.pop()
	op = operand.pop()
	result = parse(right, left, op)
	numbers.append(result)
	return numbers[0] if len(numbers) else None
	input = ['2+3+3-4*2+12/3', '3+4/2*3+2', '100/2+50-10/2+1000']
	expected= [4, 11, 1095]
	actual = []
	for i in input:
	output =calculate(i)
	actual.append(output)
	print("expected = {}, actual={}".format(expected, actual))

view raw amazon_math_expression_no_paranthesis.py hosted with ❤ by GitHub