四则运算表达式求值：中缀改后缀

class Solution:
  def __init__(self):
    self.operators = {'+', '-', '*', '/'}  # 集合

  def precedence(self, op: str):
    """定义运算符优先级"""
    if op in ('+', '-'):
      return 1
    if op in ('*', '/'):
      return 2
    return 0
  
  def get_value(self, a: int, b: int, op: str) -> int:
    """四则运算取值"""
    if op == "+":
      return a + b
    elif op == "-":
      return a - b
    elif op == "*":
      return a * b
    elif op == "/":  # 注意：题目没有除法运算，Python 中的除法运算符 / 总是返回一个浮点数，如果需要整数除法（即向下取整），可以使用 // 运算符
      return int(a / b)
    return 0
  
  def infix_to_postfix(self, s: str) -> list:
    """中缀表达式转后缀表达式"""
    s = s.replace(' ', '') # 移除空格
    stack = []  # 运算符栈
    result = []  # 后缀表达式以列表表示
    i = 0
    while i < len(s):
      if s[i].isdigit():
        # 遇到操作数直接打印
        j = i + 1
        while j < len(s) and s[j].isdigit():
          j += 1
        num = s[i:j]
        result.append(num)
        i = j  # 注意：走一大步
        continue
      elif s[i] in self.operators:
        # 遇到加减乘除：栈空否，空进栈，不空看优先级重复比较
        while stack and stack[-1] != '(' and self.precedence(stack[-1]) >= self.precedence(s[i]):
            result.append(stack.pop())  # 注意：这里不断重复比较是精华
        stack.append(s[i])
      elif s[i] == '(':
        # 遇到左括号：进栈
        stack.append(s[i])
      elif s[i] == ')':
        # 遇到右括号：出栈直到左括号
        while stack and stack[-1] != '(':
          result.append(stack.pop())
        stack.pop()  # 弹出左括号
      # 继续扫描
      i += 1
    # 收尾，全部出栈
    while stack:
      result.append(stack.pop())  # 注意：不能 extend
    return result

  def evaluate_postfix(self, postfix: list) -> int:
    """后缀表达式求值"""
    stack = []  # 操作数栈
    for token in postfix:
      if token in self.operators:
        b = stack.pop()
        a = 0
        if stack:
          a = stack.pop() # 正常两数计算，而非负数
        val = self.get_value(a, b, token)
        stack.append(val)
      else:
        stack.append(int(token))
    return stack.pop()

  def calculate(self, s: str) -> int:
    """完整计算流程"""
    postfix = self.infix_to_postfix(s)
    result = self.evaluate_postfix(postfix)
    return result

class Solution:

  def precedence(self, op: str):
    """修改：定义运算符优先级，一元运算符目前最高"""
    if op in {'+', '-'}:
      return 1
    elif op in {'*', '/'}:
      return 2
    elif op in {'~'}:
      return 3
    return 0
  
  def get_value(self, a: int, b: int, op: str) -> int:
    """修改：四则运算取值，加上一元运算"""
    if op == "+":
      return a + b
    elif op == "-":
      return a - b
    elif op == "*":
      return a * b
    elif op == "/":  # 注意：题目没有除法运算，Python 中的除法运算符 / 总是返回一个浮点数，如果需要整数除法（即向下取整），可以使用 // 运算符
      return int(a / b)
    elif op == "~":
      return -b  # 一元运算取第二个操作数
    return 0
  
  def tokenize(self, s: str) -> list:
    """修改：分词，识别负号是二元运算还是一元运算"""
    s = s.replace(' ', '') # 移除空格
    result = []
    i = 0
    while i < len(s):
      if s[i] == '-':
        # 表示一元运算的负号出现在以下情况：
        # 1. 表达式开头: "-5 + 3"
        # 2. 左括号后: "(-5 + 3)" 或 "(-5)"
        # 3. 其他运算符后: "3 * -5" 或 "3 + -5" （可以支持，虽然一般不允许这样连续）
        if i == 0 or (s[i - 1] in {'(', '+', '-', '*', '/'}):
          result.append('~') # 一元运算
        else:
          result.append('-') # 二元运算
      elif s[i].isdigit():
        # 识别数字
        j = i + 1
        while j < len(s) and s[j].isdigit():
          j += 1
        result.append(s[i:j])
        i = j
        continue
      elif s[i] in {'+', '-', '*', '/', '(', ')'}:
        # 识别其他运算符
        result.append(s[i])
      i += 1
    return result
  
  def infix_to_postfix(self, tokens: list) -> list:
    """修改：中缀表达式转后缀表达式，仅小小修改"""
    stack = []  # 运算符栈
    result = []  # 后缀表达式以列表表示
    for token in tokens:
      if token in {'+', '-', '*', '/', '~'}:
        # 遇到加减乘除～：栈空否，空进栈，不空看优先级重复比较
        while stack and stack[-1] != '(' and self.precedence(stack[-1]) >= self.precedence(token):
          result.append(stack.pop())
        stack.append(token)
      elif token == '(':
        stack.append(token)
      elif token == ')':
        while stack and stack[-1] != '(':
          result.append(stack.pop())
        stack.pop()  # 弹出左括号
      else:
        # 遇到操作数直接打印
        result.append(token)
    # 收尾，全部出栈
    while stack:
      result.append(stack.pop())  # 注意：不能 extend
    return result

  def evaluate_postfix(self, postfix: list) -> int:
    """修改：后缀表达式求值，对一元运算取值做特化"""
    stack = []  # 操作数栈
    for token in postfix:
      if token in {'+', '-', '*', '/', '~'}:
        b = stack.pop()
        a = 0
        if token != '~':
          a = stack.pop()
        val = self.get_value(a, b, token)
        stack.append(val)
      else:
        stack.append(int(token))
    return stack.pop()

  def calculate(self, s: str) -> int:
    """完整计算流程"""
    tokens = self.tokenize(s)
    # print(tokens)
    postfix = self.infix_to_postfix(tokens)
    # print(postfix)
    result = self.evaluate_postfix(postfix)
    return result