胖哥网站的建设目标,中国正国级名单,初级网站开发的自我推荐,企业网站建设亮点括号匹配问题和逆波兰表达式求值问题
基于上一节已经使用python代码对栈进行了简单的实现#xff0c;这一节我们在其基础上解决两个常见的问题
案例
括号匹配问题(点我直接到代码实现)逆波兰表达式求值问题(点我直接到代码实现)
括号匹配问题
在给定的字符串中#xff0…括号匹配问题和逆波兰表达式求值问题
基于上一节已经使用python代码对栈进行了简单的实现这一节我们在其基础上解决两个常见的问题
案例
括号匹配问题(点我直接到代码实现)逆波兰表达式求值问题(点我直接到代码实现)
括号匹配问题
在给定的字符串中编写程序实现确定该字符串类的括号是否匹配的问题 使用栈解决这个问题的思路 括号匹配python代码实现
from Structure.linear.Stack import Stackdef is_matched_brackets(_strNone):stack Stack()for s in _strs:# If the sub-str is (, push it into the stackif s (:stack.push(s)# If it is ), try to pop a ( from the stackelif s ):pop_a_left stack.pop()# If hadnt popped a (, return falseif not pop_a_left:return Falseif stack.len 0:return Truereturn False# _strs ()(Shanghai)(Changan))(
# _strs ())(
_strs (())()
print(fIs the brackets matched in {_strs} ? {is_matched_brackets(_strs)})然后这里导入的Stack是上一节栈的实现写的代码也就使用到了pop和push的方法以及len属性代码量也不算很多我就直接复制过来了方便查看这里功能实现起来也是非常的简单就不做过多赘述来解释了。
class Node:def __init__(self, item):self.item itemself.next Noneclass Stack:def __init__(self):self.head Noneself.len 0def is_empty(self):return not self.len# def length(self):# return self.lendef push(self, item):Push an element into the stacknode Node(item)node.next self.headself.head nodeself.len 1def pop(self):Pop a value from the stack top# if not self.head:# raise IndexError(pop from empty list)cur self.headif self.head:self.head self.head.nextself.len - 1return cur逆波兰表达式
在定义逆波兰表达式求值问题之前我们先来看一下中缀表达式是什么
定义中缀表达式是一个通用的算术或逻辑公式表示方法二元运算符总是会在两个操作数的中间
举个栗子
例如1 3 * 2和2 - ( 1 3 )运算符( - * /)都是在两个值的中间
这种表达式虽然对于我们人类来说观看和使用起来都是非常简单的但是对于计算机并不太友好这是因为这种表达式并不是有顺序的在运算时还可能涉及到很多优先级顺序的判断
因此我们引入了中缀表达式转后缀表达式的概念这里的后缀表达式就是我们所说的逆波兰表达式
简介逆波兰式Reverse Polish notationRPN或逆波兰记法也叫后缀表达式将运算符写在操作数之后
逆波兰表达式的定义描述看起来晦涩难懂简单的说就是将运算符写在操作数之后的表达式对定义描述感兴趣的同学可以自行百度一下这里我们用几个例子直观的感受一下 通过结果看转换前的状态会比较好理解
a b → ab先看操作符一个操作符对应两个值加号对应a 和 b相加得到aba (b - c) → abc-先看操作符一个操作符对应两个值减号-对应离他最近的bc因此先计算b - c再看加号也对于两个值就是a 和 (b - c)因此为 a (b - c)a (b -c) * d → abc-d*先看操作符秉承操作运算的先后顺序减号-对应b - c然后乘号*对应的是(b - c)*d最后加号对应的也是两个值a 和 (b - c)*d相加即可得到a (b - c) * da * (b - c) d → abc-*d同样以操作符为中心寻找数字减号-对应b 和 c相减得到(b - c)乘号*对应a 和 (b - c)相乘得到a * (b - c)加号对应a * (b - c)和 d相加得到结果 a * (b - c) d
代码实现思路
如果当前字符为变量或者为数字则压栈如果是运算符则将栈顶两个元素弹出作相应运算结果再入栈最后当表达式扫描完后栈里的就是结果。
实现流程图 python代码实现 这里先要写一个实现栈的类方法也可以参照前期的栈实现文章
class Node:def __init__(self, item):self.item itemself.next Noneclass Stack:def __init__(self):self.head Noneself.len 0def is_empty(self):return not self.len# def length(self):# return self.lendef push(self, item):Push an element into the stacknode Node(item)node.next self.headself.head nodeself.len 1def pop(self):Pop a value from the stack top# if not self.head:# raise IndexError(pop from empty list)cur self.headif self.head:self.head self.head.nextself.len - 1return curfrom Structure.linear.Stack import Stackdef reverse_polish_notation(_strs):nums Stack()for s in _strs:if s not in [, -, *, /]:nums.push(s)else:num1 nums.pop().itemnum2 nums.pop().item# This equals to num2 [-*/] num1res eval(str(num2)sstr(num1))nums.push(res)return nums.pop().item# 2*(18-13)-12/4 2*5 - 3 7
_strs 2, 18, 13, -, *, 12, 4, /, -
result reverse_polish_notation(_strs)
print(fThe computation of {_strs} is {2*(18-13)-12/4})
print(fThe result is {result})运行结果
The computation of (2, 18, 13, -, *, 12, 4, /, -) is 7.0
The result is 7.0实现过程比较简单就不过多赘述了
