1

I'm trying to implement this right-to-left evaluation algorithm of a postfix expression but I can't seem to get it to work.

for each token in the reversed postfix expression:
  if token is an operator:
    push token onto the operator stack
    pending_operand ← False
  else if token is an operand:
    operand ← token
    if pending_operand is True:
      while the operand stack is not empty:
        operand_1 ← pop from the operand stack
        operator ← pop from the operator stack
        operand ← evaluate operator with operand_1 and operand
    push operand onto the operand stack
    pending_operand ← True
result ← pop from the operand stack

From wikipedia.

This is how the steps are illustrated:

15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7 1 1 + − ÷ 3 × 2     2 + − =
15 7 1 1 + − ÷ 3 ×         4 − =
15 7     2 − ÷ 3 ×         4 − =
15         5 ÷ 3 ×         4 − =
             3 3 ×         4 − =
                 9         4 − =
                             5

I don't really get how this follows from the algorithm. I keep getting the wrong answer trying to evaluate the expression 15 7 1 1 + − ÷ 3 × 2 1 1 + + − (should be 5). I've spent hours trying to get it working in assembly and I tried manually going through it but I keep getting the wrong answer. I think part of if lies in operate(operand_1, operand), ruled out. Anyways, I threw together this piece of JavaScript to show my interpretation of the algorithm, since it's way clearer than assembly.

const   rpn = [15, 7, 1, 1, '+', '-', '/', 3, '*', 2, 1, 1, '+', '+', '-'];
const   operator_Stack = [];
const   operand_Stack = [];
let     pending = false;

for (i = rpn.length - 1; i >= 0; i--) {
    const   token = rpn[i];
    if (typeof token === "string") {
        operator_Stack.push(token);
        pending = false;
    } else {
        let operand = token;
        if (pending) {
            while (operand_Stack.length > 0) {
                let operand_1 = operand_Stack.pop();
                let operator = operator_Stack.pop();
                let expr = operand + " " + operator + " " + operand_1;
                console.log(expr);
                operand = eval(expr);
            }       
        }
        operand_Stack.push(operand);
        pending = true;
    }
}
console.log("The expression evaluates to: " + operand_Stack.pop());

This evaluates the following expression in the following order:

"1 + 1"
"2 + 2"
"1 + 1"
"2 - 3"
"-1 / 4"
"7 * -0.25"
"15 - -1.75"

The first three evaluations appear to be correct. Then things start to go wrong.

As a binary tree 15 7 1 1 + − ÷ 3 × 2 1 1 + + − would look like this

            [-]
           /   \
         [*]    [+]
        / \    /   \
      [/] [3] [2]  [+]
      / \          /  \
   [15] [-]      [1]  [1]
        / \
     [7]  [+]
         /   \
       [1]   [1]            

The correct order of evaluation should be:

1 + 1
2 + (1 + 1)
1 + 1
7 - (1 + 1)
15 / (7 - 2)
3 * (15 / 5)
9 - 4

To me, my JavaScript code implements the algorithm as it's stated. Yet obviously it's not correct. As I see there are two possibilities, the algorithm is wrong or, more likely, my interpretation is. Problem is, I can't figure out which of the two it is.

What is it that I'm missing?

  • 1
    Please don't use txtspk in Stack Exchange posts. Full English words only, please. Reserve the txtspk for your phone texts. – Robert Harvey Jan 18 '18 at 3:25
  • Does your Javascript produce the correct answer? If it does, just step through the code and watch the variables. – Robert Harvey Jan 18 '18 at 3:27
  • No. This is my interpretation of the algorithm quoted from Wikipedia, which does not result in the correct answer. – CervEd Jan 18 '18 at 3:42
  • 1
    Neither the algorithm nor your implementation seems obviously incorrect. Though note that left-to-right evaluation of RPN expressions is much simpler than this algorithm. Questions about problems with your code belong on Stack Overflow. But before you ask there, do more debugging. Print the contents of the stacks for each iteration. Where are the discrepancies? Just saying “I keep getting the wrong answer” isn't helpful. And try simpler inputs first. What is the simplest example that can demonstrate the problem? After you've done this necessary work, you probably won't have to ask on SO… – amon Jan 18 '18 at 7:54
  • Thanks for the reply +amon. I did note that. Since I'm using a stack to store the expression I thought the right-left made more sense. My question is about the algorithm, not the code, and so SO didn't seem like the right place. The code merely serves to illustrate my interpretation. I added some further information, how it evaluates and the correct order. The algorithm fails on the 4th step. Any help is greatly appreciated, even if it´s just a specific question. – CervEd Jan 18 '18 at 11:00
2

You have a somewhat complicated program, which produces an unexpected output. It seems to work correctly in the first steps, but somewhere it goes wrong. Where? First thing you do, it to reduce the input to the simplest possible which still produces an error.

Manually removing sub-expression, I ended up with:

rpn = [7, 2, '-'];

This is 7 - 2 and should obviously result in 5. But the program actually produces -5. A possible explanation for this could be it actually inverts the operands, since 2 - 7 = -5. This hypothesis is easy to test now by using division. E.g. [10, 2, '/'] is 10/2 which is 5, but if we run it we get 0.2 which happen to be 2/10. So clearly the operands are switched. Now look at the line in the algorithm:

operand ← evaluate operator with operand_1 and operand

This line is perhaps ambiguous since it doesn't explicitly specify the order of operands. But operand_1 is the one which is first popped which means the one last pushed. In other words, in [7, 2, '-'], operand is 2 and operand_1 is 7. In your implementation you have operand_1 <operator> operand which is reverse of what you expect.

The reason you don't see the error in the first three iterations is that the order of the operands doesn't matter for +.

After checking with the operands reversed, there seem to be a second problem which is with the algorithm itself. Consider this input:

[15, 7, 2, '-', '/', 3, '*']

This should correspond to 15 / (7-2) * 3 which should be 9, but the program returns 25. It seems it evaluates as (7-2) / 3 * 15.

According to the algorithm as stated, after resolving 7 2 -, it should then continue resolving from the stack until the operand stack is empty, and only then continue to process 15. Since 3 is on the operand stack at this point, you get 5 / 3 which is wrong as far as I can tell.

Wikipedia does not provide a reference for the algorithm, but looking at the edit history of the page, it seems someone edited the fist line from "reversed prefix expression" to "reversed postfix expression". Possibly there have been some confusion because reversing a prefix notation as a whole is not the same as postfix aka reverse polish.

Consider this infix notation:

(2+2)/(7-2)*3

In prefix notation (aka Polish):

* / + 2 2 - 7 2 3

In postfix notation (aka reverse Polish):

2 2 + 7 2 - / 3 *

Note that this is different from just reversing the prefix notation as a whole! But Wikipedia seem to mix this up. I also note the algorithm specified by Wikipedia for resolving prefix notation is the same as the left-to-right algorithm for postfix notation. But since these are not the same as shown above, I believe the algorithm is wrong in the second context.

Reverse polish notation is not really amenable to right-to-left processing. If you want to use right-to-left processing you should consider using prefix notation as the input.

  • That line on wikipedia is definitely ambiguous - maybe it was kept close to the phrasing of the left-to-right example above. It should probably pop operand_2 from the stack if it's trying to be consistent – Useless Jan 18 '18 at 13:45
  • While I'm glad you helped me establish the order of the operands in the evaluation, this is not the source of error but thank you for ruling that out, albeit in a somewhat condescending tone. – CervEd Jan 18 '18 at 14:21
  • @CervEd: Are you saying the operand order wasn't wrong? Why did you change it in the source code then? – JacquesB Jan 18 '18 at 15:36
  • @JacquesB No I'm saying it was wrong but that's not the problem. It evaluates to 16.5. This is actually the way I originally wrote it in assembly – CervEd Jan 18 '18 at 15:51
  • I followed your advice and found that the algorithm works for 15, 5, /, 3, *, 2, 1, 1, +, +, - but not 15, 7, 2, -, /, 3, *, 2, 1, 1, +, +, -. I'm starting to think the problem is with algorithm and not with my understanding of it – CervEd Jan 18 '18 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.