编程的本质来自算法，算法的本质来自数学。编程只是数学问题的代码。算法是一门既不容易学也不容易掌握的学科。括号匹配这是Leetcode的第20题，也是一道单调栈的简单题。给定一个仅由'(',')','{','}','[',']'组成的字符串，检查该字符串是否有效。有效的字符串是：左括号必须用相同类型的右括号括起来。左括号必须以正确的顺序闭合。请注意，空字符串被视为有效字符串。输入："{[]}"输出：true单调栈的关键在于如何入栈和出栈。使用栈保存匹配的左括号，将字符串从左到右扫描一次，当扫描到左括号时，将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果匹配，则继续扫描字符串的其余部分。如果在扫描过程中出现右括号不匹配或者栈中没有数据，则说明格式不合法。当扫描完所有的括号后，如果栈为空，则说明该字符串是合法格式；否则，这意味着不匹配的左括号是非法格式。defisValid(s):""":types:str:rtype:bool"""stack=[]paren_map={')':'(',']':'[','}':'{'}forcins:ifcnotinparen_map:stack.append(c)elifnotstackorparen_map[c]!=stack.pop():returnFalsereturnnotstacks=input('Enterbracketcharacters:')print(isValid(s))这道题也可以用python的replace函数用空字符替换成对匹配的括号，然后依次进行，如果括号有效，则经过有限的循环次数后字符串一定为空，最后判断字符串是否为空。这个想法很简单，实现也很容易：defisValid(s):""":types:str:rtype:bool"""n=len(s)ifn==0:returnTruewhile'()'insor'{}'insor'[]'ins:s=s.replace('{}','').replace('[]','').replace('()Val','')returns==''数学表达式首先，让我们看一下数学表达式的三种形式：前缀表达式、中缀表达式和后缀表达式。中缀表达式（InfixExpression）是我们常用的写法，带括号。前缀表达式（PrefixExpression）要求运算符出现在操作数的前面。后缀表达式（PostfixExpression）要求操作数出现在操作数的后面，一般这两个表达式不会出现在括号中。后缀表达式，也称为反向波兰语。数学表达式的三种形式举例如下：中缀表达式运算符在中缀形式的操作数中间（例如：3+4），中缀表达式是一种常用的算术表达式方法。与前缀表达式（例如：+12）或后缀表达式（例如：12+）相比，中缀表达式不易被计算机解析，但由于符合人们的通用用法，所以仍被许多编程语言所使用。下面的问题转成：如何使用栈实现中缀表达式的求值，例如：34+13*9+44-12/3=191思路：使用两个栈，其中一个用来存放操作数，另一个用于保存运算符。我们从左到右遍历表达式。遇到数字，直接压入操作数栈；当我们遇到一个运算符时，我们将它与运算符堆栈的顶部元素进行比较。如果其优先级高于运算符栈顶元素，则将当前运算符压入栈中；如果其优先级低于或等于运算符栈顶元素，则从运算符栈中取出栈顶运算符，并从操作数栈顶取出2个操作数，然后进行计算，将计算结果压入操作数栈，继续比较。definfix_evaluator(infix_expression:str)->int:'''这个是中缀表达式求值的函数：参数infix_expression：中缀表达式需要用空格分隔'''token_list=infix_expression.split()print(token_list)#运算符优先级dictionarypre_dict={'*':3,'/':3,'+':2,'-':2,'(':1}#运算符栈operator_stack=[]#操作数栈operand_stack=[]fortokenintoken_list:#数字入操作数栈print(token)#10or-10iftoken.isdecimal()ortoken[1:].isdecimal():operand_stack.append(int(token))#左括号入操作数栈eliftoken=='(':operator_stack.append(token)#当遇到右括号时，必须将左括号以上的运算符全部弹出栈顶，才能计算eliftoken==')':top=operator_stack.pop()whiletop!='(':#每次弹出一个运算符，都要弹出两个操作数进行求值#注意弹出操作数的顺序是相反的，先弹出的数是op2op2=operand_stack。pop()op1=operand_stack.pop()#计算出的值应该被推回操作数栈#这里使用的函数get_value定义如下operand_stack.append(get_value(top,op1,op2))#弹出下一个栈Topoperatortop=operator_stack.pop()#遇到operator，必须pop优先级不低于它的所有栈顶。评估eliftokenin'+-*/':whileoperator_stackandpre_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))#不要忘记在operato的末尾将当前operator压入栈中r_stack.append(token)#表达式遍历完成后，栈中剩余的算子也需要取值whileoperator_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)returnoperand_stack[0]defget_value(operator:str,op1:int,op2:int):'''这是四个算术函数：参数运算符：运算符：参数op1：左操作数：参数op2：右操作数'''ifoperator=='+':returnop1+op2elifoperator=='-':returnop1-op2elifoperator=='*':returnop1*op2elifoperator=='/':returnop1/op2#用一个例子试试，得到结果17.0print(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*|[\+\-\*\/\(\)]。importres='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
