Expression Parsing¶

Table of Contents¶

150. Evaluate Reverse Polish Notation¶

LeetCode | LeetCode CH (Medium)
Tags: array, math, stack
Steps for the list ["2", "1", "+", "3", "*"]:

token	action	stack
`2`	push	`[2]`
`1`	push	`[2, 1]`
`+`	pop	`[3]`
`3`	push	`[3, 3]`
`*`	pop	`[9]`

150. Evaluate Reverse Polish Notation - Python Solution

from typing import List


# Stack
def evalRPN(tokens: List[str]) -> int:
    stack = []

    for c in tokens:
        if c == "+":
            stack.append(stack.pop() + stack.pop())
        elif c == "-":
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif c == "*":
            stack.append(stack.pop() * stack.pop())
        elif c == "/":
            a, b = stack.pop(), stack.pop()
            stack.append(int(b / a))
        else:
            stack.append(int(c))

    return stack[0]


print(evalRPN(["2", "1", "+", "3", "*"]))  # 9
print(evalRPN(["4", "13", "5", "/", "-"]))  # 2
print(evalRPN(["18"]))  # 18
print(evalRPN(["4", "3", "-"]))  # 1

1006. Clumsy Factorial¶

LeetCode | LeetCode CH (Medium)
Tags: math, stack, simulation

224. Basic Calculator¶

LeetCode | LeetCode CH (Hard)
Tags: math, string, stack, recursion

224. Basic Calculator - Python Solution

# Stack
def calculate(s: str) -> int:
    stack = []
    result = 0
    number = 0
    sign = 1

    for char in s:
        if char.isdigit():
            number = number * 10 + int(char)

        elif char == "+":
            result += sign * number
            number = 0
            sign = 1
        elif char == "-":
            result += sign * number
            number = 0
            sign = -1

        elif char == "(":
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif char == ")":
            result += sign * number
            number = 0
            result *= stack.pop()  # pop sign
            result += stack.pop()  # pop previous result

    result += sign * number

    return result


print(calculate("(1+(4+5+2)-3)+(6+8)"))  # 23

227. Basic Calculator II¶

LeetCode | LeetCode CH (Medium)
Tags: math, string, stack

227. Basic Calculator II - Python Solution

# Stack
def calculate(s: str) -> int:
    stack = []
    num = 0
    sign = "+"

    for index, char in enumerate(s):
        if char.isdigit():
            num = num * 10 + int(char)

        if char in "+-*/" or index == len(s) - 1:
            if sign == "+":
                stack.append(num)
            elif sign == "-":
                stack.append(-num)
            elif sign == "*":
                stack.append(stack.pop() * num)
            elif sign == "/":
                stack.append(int(stack.pop() / num))
            sign = char
            num = 0

    return sum(stack)


s = "3+2*2"
print(calculate(s))  # 7

726. Number of Atoms¶

LeetCode | LeetCode CH (Hard)
Tags: hash table, string, stack, sorting

1106. Parsing A Boolean Expression¶

LeetCode | LeetCode CH (Hard)
Tags: string, stack, recursion

591. Tag Validator¶

LeetCode | LeetCode CH (Hard)
Tags: string, stack

736. Parse Lisp Expression¶

LeetCode | LeetCode CH (Hard)
Tags: hash table, string, stack, recursion

1096. Brace Expansion II¶

LeetCode | LeetCode CH (Hard)
Tags: string, backtracking, stack, breadth first search

1896. Minimum Cost to Change the Final Value of Expression¶

LeetCode | LeetCode CH (Hard)
Tags: math, string, dynamic programming, stack

770. Basic Calculator IV¶

LeetCode | LeetCode CH (Hard)
Tags: hash table, math, string, stack, recursion

770. Basic Calculator IV - Python Solution

from collections import defaultdict
from typing import List


# Stack
class Solution:
    def __init__(self):
        self.operators = set(["+", "-", "*"])

    def basicCalculatorIV(
        self, expression: str, evalvars: List[str], evalints: List[int]
    ) -> List[str]:
        evalmap = dict(zip(evalvars, evalints))
        tokens = self.parse_expression(expression)
        result_terms = self.evaluate(tokens, evalmap)
        return self.format_result(result_terms)

    def parse_expression(self, expression):
        tokens = []
        i = 0
        while i < len(expression):
            if expression[i].isalnum():  # Variable or digit
                start = i
                while i < len(expression) and (
                    expression[i].isalnum() or expression[i] == "_"
                ):
                    i += 1
                tokens.append(expression[start:i])
            elif expression[i] in self.operators or expression[i] in "()":
                tokens.append(expression[i])
                i += 1
            elif expression[i] == " ":
                i += 1  # skip whitespace
        return tokens

    def evaluate(self, tokens, evalmap):
        def apply_operator(op, b, a):
            if op == "+":
                return self.add_terms(a, b)
            elif op == "-":
                return self.add_terms(a, self.negate_terms(b))
            elif op == "*":
                return self.multiply_terms(a, b)

        def process_token(token):
            if token.isalnum():
                if token in evalmap:
                    stack.append({(): evalmap[token]})
                elif token.isdigit():
                    stack.append({(): int(token)})
                else:
                    stack.append({(token,): 1})
            elif token == "(":
                ops.append(token)
            elif token == ")":
                while ops and ops[-1] != "(":
                    operate()
                ops.pop()
            else:
                while (
                    ops
                    and ops[-1] in precedence
                    and precedence[ops[-1]] >= precedence[token]
                ):
                    operate()
                ops.append(token)

        def operate():
            if len(stack) < 2 or not ops:
                return
            b = stack.pop()
            a = stack.pop()
            op = ops.pop()
            stack.append(apply_operator(op, b, a))

        stack = []
        ops = []
        precedence = {"+": 1, "-": 1, "*": 2}

        for token in tokens:
            process_token(token)

        while ops:
            operate()
        return self.combine_terms(stack[-1])

    def add_terms(self, a, b):
        result = defaultdict(int, a)
        for term, coef in b.items():
            result[term] += coef
        return dict(result)

    def negate_terms(self, a):
        return {term: -coef for term, coef in a.items()}

    def multiply_terms(self, a, b):
        result = defaultdict(int)
        for term1, coef1 in a.items():
            for term2, coef2 in b.items():
                new_term = tuple(sorted(term1 + term2))
                result[new_term] += coef1 * coef2
        return dict(result)

    def combine_terms(self, terms):
        result = defaultdict(int)
        for term, coef in terms.items():
            if coef != 0:
                result[term] = coef
        return dict(result)

    def format_result(self, result_terms):
        result = []
        for term in sorted(result_terms.keys(), key=lambda x: (-len(x), x)):
            coef = result_terms[term]
            if coef != 0:
                term_str = "*".join(term)
                if term_str:
                    result.append(f"{coef}*{term_str}")
                else:
                    result.append(str(coef))
        return result


calculator = Solution()
expression = "e + 8 - a + 5"
evalvars = ["e"]
evalints = [1]
print(calculator.basicCalculatorIV(expression, evalvars, evalints))
# ['-1*a', '14']

439. Ternary Expression Parser¶

LeetCode | LeetCode CH (Medium)
Tags: string, stack, recursion

772. Basic Calculator III¶

LeetCode | LeetCode CH (Hard)
Tags: math, string, stack, recursion

772. Basic Calculator III - Python Solution

# Stack
def calculate(s: str) -> int:
    def helper(index):
        stack = []
        num = 0
        sign = "+"

        while index < len(s):
            char = s[index]
            if char.isdigit():
                num = num * 10 + int(char)
            if char == "(":
                num, index = helper(index + 1)
            if char in "+-*/)" or index == len(s) - 1:
                if sign == "+":
                    stack.append(num)
                elif sign == "-":
                    stack.append(-num)
                elif sign == "*":
                    stack.append(stack.pop() * num)
                elif sign == "/":
                    stack.append(int(stack.pop() / num))  # 向零取整
                num = 0
                sign = char
            if char == ")":
                break
            index += 1

        return sum(stack), index

    s = s.replace(" ", "")
    result, _ = helper(0)

    return result


s = "2*(5+5*2)/3+(6/2+8)"
print(calculate(s))  # 21

1087. Brace Expansion¶

LeetCode | LeetCode CH (Medium)
Tags: string, backtracking, breadth first search

1597. Build Binary Expression Tree From Infix Expression¶

LeetCode | LeetCode CH (Hard)
Tags: string, stack, tree, binary tree

1628. Design an Expression Tree With Evaluate Function¶

LeetCode | LeetCode CH (Medium)
Tags: array, math, stack, tree, design, binary tree