栈，是一种操作受限的线性表，其操作规则为：后进者先出，先进者后出。
目录
题目需求：
给定一个字符串，形如“1+6*5/3-8”，根据其内容，计算结果，此例结果为3。
解题思路：
1、去除空格字符、在运算符两边添加空格、分割成list(形如：['1', '+', '6', '*', '5', '/', '3', '-', '8'])。
2、申请两个栈，分别用于存放数字、运算符。
3、从左到右每次读取s中的一个元素：
3.1、如果是数字，则转化为整形压入数字栈；
3.2、如果是运算符，则与当前运算符栈顶元素比较，优先级大于栈顶元素则入栈；
3.3、优先级小于等于当前栈顶元素，则：
3.3.1、取出两个数字，与当前栈顶元素进行运算，结果压入数字栈，
3.3.2、重复此过程，直到清空当前运算符栈；
3.4、然后，将当前运算符压入运算符栈。
4、对最终的两个栈，进行提取元素并计算得出最终结果。
一、定义一个栈
class Stack(object):
def __init__(self, max_length = 100):
self._max_length = max_length
self._stack = []
self.count = 0
def push(self, x):
if self.count < self._max_length:
self._stack.append(x)
self.count += 1
def pull(self):
if self.count > 0:
x = self._stack.pop()
self.count -= 1
return x
return None
def sprint(self):
for c in self._stack:
print(c)
二、编写四则运算代码
def arith_ont_step(a,b,op):
if op == '+':
return a+b
elif op == '-':
return a-b
elif op == '*':
return a*b
elif op == '/':
return a/b
def arithmetic(s):
"""
根据给定四则运算的字符串s,求其计算结果
方法：
1、去除空格字符、添加空格、分割成list(形如：['1', '-', '2', '+', '1', '*', '5'])。
2、申请两个栈，分别用于存放数字、运算符。
3、从左到右每次读取s中的一个元素：
3.1、如果是数字，则转化为整形压入数字栈；
3.2、如果是运算符，则与当前运算符栈顶元素比较，优先级大于栈顶元素则入栈；
3.3、优先级小于等于当前栈顶元素，则：
3.3.1、取出两个数字，与当前栈顶元素进行运算，结果压入数字栈，
3.3.2、重复此过程，直到清空当前运算符栈；
3.4、然后，将当前运算符压入运算符栈。
4、对最终的两个栈，进行提取元素并计算得出最终结果。
"""
ops = ['+','-','*','/']
prority = {0:0,1:0,2:1,3:1}
s = s.replace(' ','')
if s[0] == '-':
s = '0' + s
elif s[0] == '+':
s = s[1:]
for sp in ops:
s = s.replace(sp,' '+sp+' ')
s = s.split(' ')
stack_num, stack_ope = Stack(), Stack()
for sym in s:
if sym in ops:
if stack_ope.count == 0:
stack_ope.push(sym)
else:
while stack_ope.count>0:
sym_top = stack_ope.pull()
if prority[ops.index(sym_top)] >= prority[ops.index(sym)]:
a = stack_num.pull()
b = stack_num.pull()
temp_result = arith_ont_step(b,a,sym_top)
stack_num.push(temp_result)
else:
stack_ope.push(sym_top)
break
stack_ope.push(sym)
else:
stack_num.push(int(sym))
# 然后对当前两个栈进行出栈计算
result = stack_num.pull()
while stack_ope.count>0:
op = stack_ope.pull()
b = stack_num.pull()
result = arith_ont_step(b,result,op)
return result
三、测试结果
原文链接:/oYeZhou/article/details/105635406
