python 栈实现 加减乘除_数据结构与算法（六）：基于栈实现简单的四则运算

栈，是一种操作受限的线性表，其操作规则为：后进者先出，先进者后出。

目录

题目需求：

给定一个字符串，形如“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

三、测试结果

原文链接:https://blog.csdn.net/oYeZhou/article/details/105635406