Introduction

Precedence (优先级): exponential > Multiplication/Division > Addition/Subtraction

Associativity (结合性): addition, subtraction, multiplication, and division are left-associated. Exponentiation is right-associated. For example, 2^3^2 = 2^{(3^2)}, not (2^3)^2.

Rules for parsing

• If the currently encountered operator is left-associated, and the precedence of the current operator is greater than the precedence of the top-of-stack operator, then the current operator should be the right child of the top-of-stack operator.

  Note: (1) The stack is used to keep track of parsed operators; (2) The parse tree should eventually be a full binary tree, and the left child node of the current operator already exists, so it is placed in the right child node.

• If the currently encountered operator is left-associated, and the priority of the current operator is less than or equal to the priority of the top-of-stack operator, then the current operator should be the parent or ancestor of the top-of-stack operator.

  Note: Pop until the current operator priority is greater than the stack top operator priority.

• If the currently encountered operator is right-associated, it shall be the right child of the top-of-stack operator.

Remark

The notion behind the rules is to place the low precedence left associative operators higher in the parse tree.

Pratt Parsing

[TODO]

Evaluating Reverse Polish Notation

• Traverse the parse tree in back order to derive a string of tokens.

• Read the string (e.g., 1 2 3 4 5 ^ ^ * 6 * +) in order. For operands, push them onto the stack. For operators, pop two numbers from the stack and push the result back onto the stack. After processing the entire string, the value of the reverse Polish notation is on the top of the stack.