Normal to RPN conversion

Question

I have a question.
Is (3+4)*(5+6+7*8)*(1*9+2*8) equal to 34 + 56 + 78 + * + 19 * 28 * + * in RPN notation?

Answer 1

There are these issues with your attempt:

• Numbers need to be separated by spaces as otherwise you create new numbers. 34 is thirty four, not three and then four. So write 3 4
• The input has 5 multiplications, yet your RPN has only 4, so that cannot be right. Notably you have mixed the operators up right after the 7. That 7 is the operand of a multiplication, not an addition. After the 7 should not have + * +, but * + *

You can apply these steps to produce RPN:

1. Add parentheses to the input so to make all operations binary (with two operands only), resolving precedence (* has precedence over +), and when precedence is equal, applying a left-associativity rule:

   (3+4)*(5+6+7*8)*(1*9+2*8)
   

   becomes:

   ((3+4)*((5+6)+(7*8)))*((1*9)+(2*8))
   

2. Write the expression as a binary tree

           ______*_____
          /            \
       __*__           _+_
      /     \         /   \
     +      _+_      *     *
    / \    /   \    / \   / \
   3   4  +     *  1   9 2   8
         / \   / \
        5   6 7   8
   

3. Produce the output from a post order traversal, using space as separator

   3 4 + 5 6 + 7 8 * + * 1 9 * 2 8 * + *
   

That's it.

Shunting-yard

A good algorithm to convert the input to RPN is the Shunting-year algorithm. Here is an implementation in JavaScript for just the operators your expression uses:

function shuntingYard(expr) {
    const precedence = {"+": 0, "*": 1, "(": -1};
    const operators = [];
    const output = [];
    
    for (const token of expr.match(/\d+|\S/g)) {
        if (token == ")") {
            while (operators.at(-1) != "(") {
                output.push(operators.pop());
            }
            operators.pop();
        } else if (token in precedence) {
            const prio = precedence[token];
            while (prio >= 0 && prio <= precedence[operators.at(-1)]) {
                output.push(operators.pop());
            }
            operators.push(token);
        } else { // It is a number
            output.push(token);
        }
    }
    return output.concat(operators).join(" ");
}

let expr = "(3+4)*(5+6+7*8)*(1*9+2*8)";
console.log(shuntingYard(expr));