聊聊栈在括号匹配和表达式求值中的应用

时间:2022-02-21 07:06:18

编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。

算法,一门既不容易入门,也不容易精通的学问。

括号匹配这是Leetcode第20题,也是一道单调的简单题。

给定一个只包括'(',')','{','}','[',']'的字符串,判断字符串是否有效。

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。

输入: "{[]}"输出: true单调栈关键在于如何入栈和出栈。

用栈保存为匹配的左括号,从左到右一次扫描字符串,当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号,如果能匹配上,则继续扫描剩下的字符串。如果扫描过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。

当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明未匹配的左括号为非法格式。

def isValid(s): 

    ""

    :type s: str 

    :rtype: bool 

    ""

    stack = [] 

    paren_map ={')':'(',']':'[','}':'{'

    for c in s: 

        if c not in paren_map: 

            stack.append(c) 

        elif not stack or paren_map[c] !=stack.pop(): 

            return False 

    return not stack 

s = input('输入括号字符:'

print(isValid(s)) 

在此题中,也可以利用python种的replace函数将成对的可匹配括号用空字符代替 ,之后依次进行 ,若是有效的括号 ,必然经过有限次循环后 ,字符串为空 ,则最后判断字符串是否为空即可。思路简单,实现也很容易:

def isValid(s): 

    ""

    :type s: str 

    :rtype: bool 

    ""

    n = len(s) 

    if n == 0: return True 

    while '()' in s or '{}' in s or '[]' in s: 

        s = s.replace('{}','').replace('[]','').replace('()Val',''

    return s == '' 

数学表达

式首先,我们来看一下数学表达式的三种形式:前缀表达式,中缀表达式,后缀表达式。

  • 中缀表达式(Infix Expression)就是我们平时常用的书写方式,带有括号。
  • 前缀表达式(Prefix Expression)要求运算符出现在运算数字的前面。
  • 后缀表达式(Postfix Expression)要求运算符出现在运算数字的后面,一般这两种表达式不出现括号。后缀表达式,又称逆波兰式。

数学表达式的三种形式示例如下:

聊聊栈在括号匹配和表达式求值中的应用

中缀表达式操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。与前缀表达式(例:+ 1 2)或后缀表达式(例:1 2 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。

下面问题转为为:如何利用栈实现中缀表达式求值,比如:34+13*9+44-12/3=191思路:利用两个栈,其中一个用来保存操作数,另一个用来保存运算符。

我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。

若比运算符栈顶元素优先级高,就将当前运算符压入栈,若比运算符栈顶元素的优先级低或者相同,从运算符栈中取出栈顶运算符,从操作数栈顶取出2个操作数,然后进行计算,把计算完的结果压入操作数栈,继续比较。

def infix_evaluator(infix_expression : str) -> int : 

    '''这是中缀表达式求值的函数 

    :参数 infix_expression:中缀表达式 需要用空格进行隔开 

    ''

    token_list = infix_expression.split() 

    print(token_list) 

    # 运算符优先级字典 

    pre_dict = {'*':3,'/':3,'+':2,'-':2, '(':1} 

    # 运算符栈 

    operator_stack = [] 

    # 操作数栈 

    operand_stack = [] 

    for token in token_list: 

        # 数字进操作数栈 

        print(token) 

        # 10或者-10的情况 

        if token.isdecimal() or token[1:].isdecimal():  

            operand_stack.append(int(token)) 

        # 左括号进运算符栈 

        elif token == '('

            operator_stack.append(token) 

        # 碰到右括号,就要把栈顶的左括号上面的运算符都弹出求值 

        elif token == ')'

            top = operator_stack.pop() 

            while top != '('

                # 每弹出一个运算符,就要弹出两个操作数来求值 

                # 注意弹出操作数的顺序是反着的,先弹出的数是op2 

                op2 = operand_stack.pop() 

                op1 = operand_stack.pop() 

                # 求出的值要压回操作数栈 

                # 这里用到的函数get_value在下面有定义 

                operand_stack.append(get_value(top,op1,op2)) 

                # 弹出下一个栈顶运算符 

                top = operator_stack.pop() 

        # 碰到运算符,就要把栈顶优先级不低于它的都弹出求值 

        elif token in '+-*/'

            while operator_stack and pre_dict[operator_stack[-1]] >= pre_dict[token]: 

                top = operator_stack.pop() 

                op2 = operand_stack.pop() 

                op1 = operand_stack.pop() 

                operand_stack.append(get_value(top,op1,op2)) 

            # 别忘了最后让当前运算符进栈 

            operator_stack.append(token) 

    # 表达式遍历完成后,栈里剩下的操作符也都要求值    

    while operator_stack: 

        top = operator_stack.pop() 

        op2 = operand_stack.pop() 

        op1 = operand_stack.pop() 

        operand_stack.append(get_value(top,op1,op2)) 

    # 最后栈里只剩下一个数字,这个数字就是整个表达式最终的结果 

    print(operand_stack) 

    print(operator_stack) 

    return operand_stack[0] 

  

def get_value(operator : str, op1 : int, op2 : int): 

    '''这是四则运算函数 

    :参数 operator:运算符 

    :参数 op1:左边的操作数 

    :参数 op2:右边的操作数 

    ''

    if operator == '+'

        return op1 + op2 

    elif operator == '-'

        return op1 - op2 

    elif operator == '*'

        return op1 * op2 

    elif operator == '/'

        return op1 / op2 

  

# 用一个例子试试,得出了结果  17.0 

print(infix_evaluator('9 + ( 3 - 1 * 2 ) * 3 + 10 / 2')) 

 

17.0 

上述程序只是使用四则运算表达式进行学习计算,但是输入需要加空格进行分隔,比如9 + ( 3 - 1 * 2 ) * 3 + 10 / 2分隔为['9', '+', '(', '3', '-', '1', '*', '2', ')', '*', '3', '+', '10', '/', '2']。

后来尝将9+(3-1*2)*3+10/2分隔为['9', '+', '(', '3', '-', '1', '*', '2', ')', '*', '3', '+', '10', '/', '2']。

后来想到了正则表达式1-9]\d*|[\+\-\*\/\(\)]。

import re 

s = '9+(3-1*2)*3+10/2' 

print(re.findall('[1-9]\d*|[\+\-\*\/\(\)]',s)) 

 

['9''+''(''3''-''1''*''2'')''*''3''+''10''/''2'

因此利用栈实现中缀表达式求值中等偏难算法题基本完成。

本文已收录 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100

原文地址:https://mp.weixin.qq.com/s/NRKXxmB86-lQcrC9DK5bKw