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)$.

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.

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