Shunting Yard algorithm for Leetcode Basic calculator

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:

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.

   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.

   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.

   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.

   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.

   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.