Python数据结构与算法中的栈详解(3)
在前两篇文章中,我们介绍了栈的基本概念、实现方式和应用场景。在本篇文章中,将深入探讨栈的一些高级应用,包中缀表达式转后缀表达式、后缀表达式求值和括号匹配等。
中缀表达式转后缀表达
中缀表达式是我们平常使用的表达式,例如3 + 4 * 5
。但是,中缀表达式不方便计算机进行计算,因此我们需要将中缀表达式转换为后缀表达式。缀表达式也称为逆波兰表达式,它的计算方式更加方便。例如,上面的中缀表达式可以转换为后缀表达式3 4 5 * +
。
下面是中缀表达式后缀表达式的算法:
- 初始化一个空栈和一个空列表。
- 从左到右扫描中缀表达式的每个素。
- 如果当前元素是数字,将其添加到输出列表中。
- 如果当前元素是左括号,将其压入栈中。
- 如果当前元素是右括号,则将栈中的元素弹出并添加到输出列表中,直到遇到左括号。左括号不添加到列表中。
- 如果当前元素是运算符,比较其与栈顶运算符的优先级:
- 如果栈顶运算符优级较高或相等,则将其弹出并添加到输出列表中,直到栈为空或栈顶运算符优先级较低。
- 将当前运算符压入栈中。
- 如果中缀表达式扫描完毕,但栈中仍有运算符,将它们依次弹出并添加到输出列表中。
- 输出列表中的元素就是后缀表达式。
下面是一个示例,演示如何将中缀表达式3 + 4 * 5
转换为后缀表达式:
- 初始化一个空栈和一个空列表。
- 从左到右描中缀表达式的每个元素。
3
是数字,将其添加到输出列表中。+
是运算符,将其压入栈中。4
是数字,其添加到输出列表中。*
是运算符,比较其与栈顶运算符的优先级,栈顶运算符+
优先级较低,将*
压入栈中。5
是数字,将其添加到输出中。- 中缀表达式扫描完毕,但栈中仍有运算符,将它们依次弹出并添加到输出列表中。栈中只有一个运算符
*
,其弹出并添加到输出列表中。 - 输出列表中的元素就是后缀表达式
3 4 5 * +
。
下面是Python代码实现中缀表达式转后缀表达式:
def infix_to_postfix(infix_expr):
# 运算符优先级
prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
# 初始化一个空栈和空列表
op_stack = []
postfix_list = []
# 将中缀表达式转换为列表
infix_list = infix_expr.split()
for token in infix_list:
if token.isdigit():
# 如果当前元素是数字,将其添加到输出列表中
postfix_list.append(token)
elif token == '(':
# 如果当前元素是左括号,将其压入栈中
op_stack.append(token)
elif token == ')':
# 如果当前元素是右括号,则将栈中的元素弹出并添加到输出列表中,直到遇到左括号
top_token =_stack.pop()
while top_token != '(':
postfix_list.append(top_token)
top_token = op_stack.pop()
else:
# 如果当前元素是运算符
while op_stack and prec[op_stack[-1]] >= prec[token]:
# 比较其与栈顶运算符的优先级
postfix_list.append(op_stack.pop())
op_stack.append(token)
# 将栈中剩余的运算符弹出并添加输出列表中
while op_stack:
postfix_list.append(op_stack.pop())
# 输出列表中的元素就是后缀表达式
return ' '.join(postfix_list)
后缀表达式求值
后表达式的计算方式更加方便,可以使用栈来实现。下面是后缀表达式求值的算法:
- 初始化一个空栈。
- 从左到右扫描后缀表达式的每个元素。
3 如果当前元是数字,将其压入栈中。 - 如果当前元素是运算符,弹出栈顶的两个元素,进行运,并将结果压入栈中。
- 扫描完毕后,栈中只剩下一个元素,即为后缀表达式的计算结果。
下面是一个示例,演示如何计算后缀表达式3 4 5 * +
的值:
- 初始化一个空栈。
- 从左到右扫描后缀表达式的每个元素。
3
是数字,将压入栈中。4
是数字,将其压入栈中。5
是数字,将其压入栈中。
-*是运算,弹出栈顶的两个元素
4和
5,进行运算
4 * 5 = 20,并将结果
20`压入栈中。+是运算符,弹出栈顶的两个元素
3和
20,进行运算
3 + 20 = 23,并将结果
23`压入栈中。- 扫描完毕后,栈中只剩下一个元素
23
,即为后缀表达式的计算结果。
下面是Python代码实现后缀表达式求值:
def postfix_eval(postfix_expr):
# 初始化一个空栈
operand_stack = []
# 将后缀表达式转换为列表 postfix_list = postfix_expr.split()
for token in postfix_list:
if token.isdigit():
# 如果当前元素是数字,将其压入栈中
operand_stack.append(int(token))
else:
# 如果当前元素是运算符,弹出栈顶的两个元素,进行运算,并将结果压入栈中
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = do_math(token, operand1, operand2)
operand_stack.append(result)
# 栈中只剩下一个元素,即为后缀表达式的计算结果
return operand_stack.pop()
def do_math(op, op1, op2):
if op == '*':
return op1 * op2
elif op == '/':
return op1 / op2
elif op == '+':
return op1 + op2
else:
return op1 - op2
括号匹配
括号匹配是栈的一个经典应用。我们可以使用栈来判断一个字符串中的括号是否匹配。下面是括号匹配的算法:
- 初始化一个空栈。
- 从左到右扫描字符串中的每个字符。
- 如果当前字符是左括号,将其压入栈中。
4.当前字符是右括号,弹出栈顶元素。如果栈顶元素不是相应的左括号,则括号不匹配。 - 扫描完毕,如果栈为空,则括号匹配。
下面是一个示例,演示如何判断字符串((()))
中的括号是否匹配:
- 初始化一个空栈。
- 从左到右扫描字符串中的每个字符。
(
是左括号,将其压入栈中。(
是左括号,将其压入栈中。(
是左括号,将其压入栈中。)
是右括号,弹出栈顶元素(
。)
是右括号,弹出栈顶元素(
。是右括号,弹出栈顶元素
(`。- 扫描完毕后,如果栈为空,则括号匹配。
下是Python代码实现括号匹配:
def par_checker(symbol_string):
# 初始化一个空栈
s = Stack()
for symbol in symbol_string if symbol == '(':
# 如果当前字符是左括号,将其压入栈中
s.push(symbol)
else:
# 如果当前字符是右括号,弹出栈顶元素。如果栈顶元素不是相应的左号,则括号不匹配
if s.is_empty():
return False
else:
s.pop()
# 扫描完毕后,如果栈为空,则括号匹配
return s.is_empty()
示例说明
下面是两个示例,演示如何使用栈实现中缀表达式转后缀表达式和后缀表达式求值:
示例1:中缀表达式转后缀表达式
def infix_to_postfix(infix_expr):
# 运算符优先级
prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
# 初始化一个空栈和一个空列表
op_stack = []
postfix_list = []
# 将中缀表达式转换为列表
infix_list = infix_expr.split()
for token in infix_list:
if token.isdigit():
# 如果当前元素是数字,将其添加到输出列表中
postfix_list.append(token)
elif token == '(':
# 如果当前元素是左括号,将其压入栈中
op_stack.append(token)
elif token == ')':
# 如果当前元素是右括号,则将栈中的元素弹出并添加到列表中,直到遇到左括号
top_token = op_stack.pop()
while top_token != '(':
postfix_list.append(top_token)
top_token = op_stack.pop()
else:
# 如果当前元素是运算符
while op_stack and prec[op_stack[-1]] >= prec[token]:
# 比较其与栈顶运算符的优先级
postfix_list.append(op_stack.pop())
op_stack.append(token)
# 将栈中剩余的运算符弹出并添加到输出列表中
while op_stack:
postfix_list.append(op_stack.pop())
# 输出列表中的元素就是后缀表达式
return ' '.join(postfix_list)
infix_expr = '3 + 4 * 5'
postfix_expr = infix_to_postfix(infix_expr)
print(postfix_expr) # 输出:3 4 5 * +
在个示例中,我们使用栈实现了中缀表达式转后缀表达式。我们将中缀表达式3 + 4 * 5
转换为后缀表达式3 4 5 * +
。
示例2:后缀表达式求
def postfix_eval(postfix_expr):
# 初始化一个空栈
operand_stack = []
# 将后缀表达式转换为列表
postfix_list = postfix_expr.split()
for token in postfix_list:
if token.isdigit():
# 如果当前元素是数字,将其压入栈中
operand_stack.append(int(token))
else:
# 如果当前元素是运算符,弹出栈顶的两个元素,进行运算,并将结果压入栈中
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = do_math(token, operand1, operand2)
operand_stack.append(result)
# 栈中只剩下一个元素,即为后缀表达式的计算结果
return operand_stack.pop()
def do_math(op, op1, op2):
if op == '*':
return op1 * op2
elif op == '/':
return op1 / op2
elif op == '+':
return op1 + op2
else:
return op1 - op2
postfix_expr = '3 4 5 * +'
result = postfix_eval(post_expr)
print(result) # 输出:23
在这个示例中,我们使用栈实现了后缀表达式求值。我们计算后缀表达式3 45 * +
的值,结果为23
。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python数据结构与算法中的栈详解(3) - Python技术站