python四则运算表达式求值
练习生 人气:0四则运算表达式求值
思路说明
使用双栈来实现——存放数值的栈 nums
与存放运算符的栈 ops
.
算法步骤
- 对原始表达式字符串
exp
进行预处理, 将其转为一个元素对应一个数值或运算符的列表explist
. - 遍历
explist
, 每个元素依次压入对应的栈中. 每次压入后, 判断当前两栈顶是否可进行乘除运算.栈顶可进行乘除运算的充要条件是,ops
栈顶为<*> ,</> 之一, 且nums
中的元素比ops
中的元素恰好多一个. 如果可以运算, 则运算, 并将运算结果压回nums
中. explist
遍历完之后, 所有乘除运算都已进行, 此时ops
中只剩加法与减法, 接下来开始另一个循环, 一直运算即可. 最后nums
中剩余的唯一元素即为表达式的值.
代码
def operation(a, b, op: str): """ 计算一次运算的结果 :param a: val :param b: val :param op: 运算符 :return: val """ if op == '+': return a+b elif op == '-': return a-b elif op == '*': return a*b elif op == '/': return a/b else: raise Exception('运算符不正确') def exp_str2list(exp: str): """ 将表达式exp:str转成list,每个元素对应一个数<num>或运算符<op>. 已知exp是标准的四则运算表达式字符串. :param exp: str,表达式 :return: list """ opset = {'+', '-', '*', '/'} # 运算符集合 flag = -1 explist = list() for i, char in enumerate(exp): # 对表达式字符串中的每个字符 if char in opset: # 若char是运算符 explist.append(exp[flag+1:i]) # 上一个运算符到当前运算符中间为数字,保存到explist flag = i # 更新flag到当前op位置 explist.append(char) # 当前op亦加入explist explist.append(exp[flag+1:]) return explist def calculate_expression(exp: str): """ 表达式求值. 计算字符串exp所代表的表达式的值, 返回一个数值 已知exp是标准的四则运算表达式字符串, 且不含括号. :param exp: str, 表达式 :return: val """ opset = {'+', '-', '*', '/'} nums = list() # 数栈 ops = list() # 运算符栈 explist = exp_str2list(exp) print(explist) for e in explist: # e入栈 if e in opset: # 若e是运算符 ops.append(e) else: nums.append(eval(e)) # 若e是优先级高的乘除法, 且 # nums与ops恰好匹配, 栈顶可以进行一次计算, 运算结果压入回nums if ops and ops[-1] in {'*', '/'} and len(nums) == len(ops) + 1: op = ops.pop() y = nums.pop() x = nums.pop() nums.append(operation(x, y, op)) # 此时explist中元素已全部遍历, 同时乘除法均已被运算, 双栈只剩加减法有待运算. 众所周知, 加减法服从结合律, 接下来一路算到底即可. while ops: op = ops.pop() y = nums.pop() x = nums.pop() x_op_y = operation(x, y, op) nums.append(x_op_y) return nums[0] if __name__ == '__main__': exp = '1*43+542+532*432' print(calculate_expression(exp)) print(eval(exp))
加载全部内容