CODEWITHSUNDEEP
algorithmnotationrpn
mmm
mmm

Reputation: 1

Normal to RPN conversion

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?

Upvotes: -1

Views: 159

Answers (1)

trincot
trincot

Reputation: 351084

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));

Upvotes: 0

Related Questions