Expression Parsing¶
Table of Contents¶
- 150. Evaluate Reverse Polish Notation (Medium)
- 1006. Clumsy Factorial (Medium)
- 224. Basic Calculator (Hard)
- 227. Basic Calculator II (Medium)
- 726. Number of Atoms (Hard)
- 1106. Parsing A Boolean Expression (Hard)
- 591. Tag Validator (Hard)
- 736. Parse Lisp Expression (Hard)
- 1096. Brace Expansion II (Hard)
- 1896. Minimum Cost to Change the Final Value of Expression (Hard)
- 770. Basic Calculator IV (Hard)
- 439. Ternary Expression Parser (Medium) 👑
- 772. Basic Calculator III (Hard) 👑
- 1087. Brace Expansion (Medium) 👑
- 1597. Build Binary Expression Tree From Infix Expression (Hard) 👑
- 1628. Design an Expression Tree With Evaluate Function (Medium) 👑
150. Evaluate Reverse Polish Notation¶
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]
def test_evalRPN():
print(evalRPN(["2", "1", "+", "3", "*"])) # 9
print(evalRPN(["4", "13", "5", "/", "-"])) # 2
print(evalRPN(["18"])) # 18
print(evalRPN(["4", "3", "-"])) # 1
1006. Clumsy Factorial¶
224. Basic Calculator¶
# 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¶
# 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¶
1106. Parsing A Boolean Expression¶
591. Tag Validator¶
736. Parse Lisp Expression¶
1096. Brace Expansion II¶
1896. Minimum Cost to Change the Final Value of Expression¶
770. Basic Calculator IV¶
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¶
# Stack
def parseTernary(expression: str) -> str:
stack = []
i = len(expression) - 1
while i >= 0:
c = expression[i]
if stack and stack[-1] == "?":
stack.pop() # remove '?'
true_val = stack.pop()
stack.pop() # remove ':'
false_val = stack.pop()
if c == "T":
stack.append(true_val)
else:
stack.append(false_val)
else:
stack.append(c)
i -= 1
return stack[-1]
if __name__ == "__main__":
assert parseTernary("T?2:3") == "2"
assert parseTernary("F?1:T?4:5") == "4"
assert parseTernary("T?T?F:5:3") == "F"
772. Basic Calculator III¶
# 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