括号匹配问题和逆波兰表达式求值问题

基于上一节已经使用python代码对栈进行了简单的实现，这一节我们在其基础上解决两个常见的问题

案例

括号匹配问题(点我直接到代码实现)逆波兰表达式求值问题(点我直接到代码实现)

括号匹配问题

在给定的字符串中，编写程序实现确定该字符串类的括号是否匹配的问题

使用栈解决这个问题的思路：

括号匹配python代码实现

from Structure.linear.Stack import Stackdef is_matched_brackets(_str=None):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 hadn't popped a '(', return falseif not pop_a_left:return Falseif stack.len == 0:return Truereturn False# _strs = "()(Shanghai)(Changan))("# _strs = "())("_strs = "(())()"print(f"Is 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 stack"""node = 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 notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）

逆波兰表达式的定义描述看起来晦涩难懂，简单的说就是将运算符写在操作数之后的表达式，对定义描述感兴趣的同学可以自行百度一下，这里我们用几个例子直观的感受一下

通过结果看转换前的状态会比较好理解：

a + b →ab+，先看操作符，一个操作符对应两个值，加号+对应a 和 b相加得到a+ba + (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 stack"""node = 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

from 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)+s+str(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(f"The computation of {_strs} is {2*(18-13)-12/4}")print(f"The result is {result}")

运行结果：

The computation of ('2', '18', '13', '-', '*', '12', '4', '/', '-') is 7.0The result is 7.0

实现过程比较简单，就不过多赘述了