Shunting Yard algorithm for Leetcode Basic calculator
Tags: leetcode, calculator, interview
Published: 2023-12-16 00:03:41

Here is the best way to solve the Leetcode Basic calculator I, II, III using Shunting Yard algorithm.

The Shunting Yard algorithm, devised by Edsger Dijkstra, is primarily used for parsing mathematical expressions, specifically for converting infix expressions (like the ones we normally use in mathematics, e.g., "3 + 4") into postfix (Reverse Polish Notation - RPN) or prefix notation.


Code:
```python
ops = {"*": 2, "/": 2, "+": 1, "-": 1}


def get_precedence(op):
    return ops[op] if op in ops else 0

def shunting_yard(input):
    ops = []
    res = []

    tokens = input.split(" ")
    for token in tokens:
        if token.isnumeric():
            res.append(token)
        elif token in "+-*/":
            while ops and get_precedence(ops[-1]) > get_precedence(token):
                res.append(ops.pop())
            ops.append(token)
        elif token == "(":
            ops.append(token)
        elif token == ")":
            while ops and ops[-1] != "(":
                res.append(ops.pop())
            ops.pop()
    res += ops[::-1]
    return res
```


The Shunting Yard algorithm is a method for parsing mathematical expressions specified in infix notation (e.g., `3 + 4`) and converting them into postfix notation (e.g., `3 4 +`) or Reverse Polish Notation (RPN). This algorithm is particularly useful because operations in postfix notation can be easily computed using a stack, allowing for efficient calculation of expressions.

Here's an explanation of each block in the `shunting_yard` function:

1. 
   ```python
   if token.isnumeric():
       res.append(token)
   ```
   - **Purpose:** This checks if the current token is a number. If it is, it's directly added to the result list. In postfix notation, numbers are placed in the same order as they appear in the infix expression.

2.
   ```python
   elif token in "+-*/":
       while ops and get_precedence(ops[-1]) > get_precedence(token):
           res.append(ops.pop())
       ops.append(token)
   ```
   - **Purpose:** This part handles operators. It uses the `get_precedence` function to determine the precedence of the operators. If the operator at the top of the operator stack (`ops`) has higher precedence than the current token, that operator is popped from the stack and added to the result list. This ensures that operators with higher precedence are evaluated first in the output expression. The current token is then pushed onto the operator stack.

3.
   ```python
   elif token == "(":
       ops.append(token)
   ```
   - **Purpose:** When an opening parenthesis is encountered, it's pushed onto the operator stack. Parentheses are used to override the usual precedence of operators to ensure the expression within them is evaluated first.

4.
   ```python
   elif token == ")":
       while ops and ops[-1] != "(":
           res.append(ops.pop())
       ops.pop()
   ```
   - **Purpose:** When a closing parenthesis is encountered, the function pops operators from the operator stack and adds them to the result list until an opening parenthesis is found. This ensures that the expression within the parentheses is correctly handled. The opening parenthesis is then popped from the stack but not added to the result list, as parentheses are not used in postfix notation.

5.
   ```python
   res += ops[::-1]
   ```
   - **Purpose:** After processing all tokens, any remaining operators on the operator stack are popped and added to the result list. This is necessary to ensure that all parts of the expression are included in the final postfix expression.

The Shunting Yard algorithm is a neat solution for converting infix expressions, which are more human-readable, into postfix expressions, which are easier for machines to evaluate.