HJ50 四则运算

本节目标：理解“HJ50 四则运算”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：53.58% 时间限制：1秒 空间限制：32M 知识点==字符串====基础数学====栈== 描述 输入一个表达式（用字符串表示），求这个表达式的值。 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

数据范围：表达式计算结果和过程中满足 ∣���∣≤1000 ∣val∣≤1000 ，字符串长度满足 1≤�≤1000 1≤n≤1000 输入描述： 输入一个算术表达式 输出描述： 得到计算结果 示例1 输入： 3+2*{1+2*[-4/(8-6)+7]} ==复制== 输出： 25

方法一 如果你想要一个简单的解决方案，使用Python，可以直接利用内置的eval函数，但这通常不是面试中期望的答案，因为它没有显示出你对算法的理解： expression = input() print(eval(expression))

方法二思路：

• 用两个变量，一个存储操作符，包括三种括号，一个用来存储参与运算的数字；
• 遍历整个字符串，可能碰到四种类型的值：
  1. 空格，路过
  2. 左括号，将括号存入操作符数组
  3. +-/，根据运算优先级，马上进行运算，对比当前运算符和前一个操作符，如果前一个操作符优先级更高，马上用前一个运算符进行运算，当然之前运行符是左括号是不能运算的，不运行。然后再判断一次当前运算符和运算符数组中的最后运算符的优先级，视情况是否马上运算，直到当前操操作符的运算优先级更低。这样的结果是操作符中也只会有+-，不会有/
  4. 右括号：算是一个优先级很高的操作，我们应该马上进行一次运算，因为第一次碰到的反向括号意味着，里面的表达式没有括号，可以直接运行了，当然括号中的运算可能有优先级的问题，但是我们在处理+-*/时，已经把能算的先算了。右括号实际上不会存在于操作符数组中，因为我们碰到一个就会计算一个，并把配对的左括号出栈；
  5. 操作数：直接放入到操作数数组，当然要考虑连续数字的问题；

处理负数

• 对这种特殊情况，对表达式进行处理，让它变得不特殊，然后再使用以前的规则
• 通过分辨负号和减号，如果是负数，在负号前加上0.
• 区分一元和二元的 - 符号：在遇到 - 符号时，判断它是作为一元运算符还是二元运算符。如果是一元运算符（即负号），您可以将其视为 0 - 数字 的形式。
• 实现一元运算的处理：在确定 - 为一元运算符后，可以通过向 values 栈添加 0，然后将 - 符号作为普通的二元减法操作符处理，这样就可以利用已有的运算逻辑来处理负数。

def evaluate(expression): def precedence(op): if op in ('+', '-'): return 1 if op in ('', '/'): return 2 return 0 def apply_op(ops, values): right = values.pop() left = values.pop() op = ops.pop() if op == '+': values.append(left + right) elif op == '-': values.append(left - right) elif op == '': values.append(left * right) elif op == '/': values.append(int(left / right)) # 注意整数除法的使用 ops, values = [], [] i = 0 while i < len(expression): if expression[i] == ' ': i += 1 elif expression[i] in '([{': ops.append(expression[i]) elif expression[i].isdigit(): val = 0 while i < len(expression) and expression[i].isdigit(): val = (val * 10) + int(expression[i]) i += 1 values.append(val) i -= 1 elif expression[i] in ')]}': while ops and ops[-1] not in '([{': apply_op(ops, values) ops.pop() # 弹出 '(' 或对应的左括号 else: while ops and precedence(ops[-1]) >= precedence(expression[i]): apply_op(ops, values) ops.append(expression[i]) i += 1 while ops: apply_op(ops, values) return values[-1]

从输入中读取表达式

expression = input().strip()

输出计算结果

print(evaluate(expression))