Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to understand the application of stack in parenthesis matching and expression evaluation". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn how to understand the application of stack in parenthesis matching and expression evaluation.

The essence of programming comes from algorithm, and the essence of algorithm comes from mathematics. Programming only codes mathematical problems.

Algorithm is a subject that is neither easy to get started nor easy to master.

Parenthesis matching this is the 20th question of Leetcode, and it is also a monotonous simple question.

Given a string that includes only'(',')','{','}','[',']', determine whether the string is valid.

A valid string must satisfy:

The left parenthesis must be closed with the same type of closing parenthesis.

The left parenthesis must be closed in the correct order.

Note that an empty string can be considered a valid string.

Input: "{[]}" output: true monotone stack the key is how to enter and exit the stack.

Save the stack as a matching left parenthesis, scan the string from left to right, and press it into the stack when the left parenthesis is scanned; when the right parenthesis is scanned, take out a left parenthesis from the top of the stack, and if it matches, continue to scan the rest of the string. If you encounter a closing parenthesis that cannot be matched during the scan, or if there is no data in the stack, it is an illegal format.

When all the parentheses are scanned, if the stack is empty, the string is in a legal format; otherwise, the unmatched left parenthesis is in an illegal format.

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 ('enter parenthesis characters:') print (isValid (s))

In this question, you can also use the replace function of python to replace pairs of matchable parentheses with empty characters, and then proceed in turn. If valid parentheses must pass through a limited number of loops, the string is empty, then you can finally judge whether the string is empty or not. The idea is simple and easy to implement:

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 =''

Mathematical expression

First of all, let's look at three forms of mathematical expressions: prefix expressions, infix expressions, and suffix expressions.

Infix expression (Infix Expression) is our usual way of writing, with parentheses.

Prefix expressions (Prefix Expression) require operators to precede operands.

Suffix expressions (Postfix Expression) require operators to appear after operands, and generally these two expressions do not have parentheses. Suffix expression, also known as inverse Polish.

Examples of the three forms of mathematical expressions are as follows:

The infix expression operator is in the middle of the Operand in the form of infix (for example: 3 + 4). Infix expression is a commonly used method of arithmetic representation. Compared with prefix expression (example: + 12) or suffix expression (example: 12 +), infix expression is not easy to be parsed by computer, but it is still used by many programming languages because it conforms to the common usage of people.

The following question turns to: how to use the stack to implement the infix expression evaluation, such as: 34 "13" 9 "44-12 ram 3" 191 idea: use two stacks, one of which is used to store operands and the other to save operators.

We traverse the expression from left to right, and when we encounter a number, we press directly into the Operand stack; when we encounter an operator, we compare it with the top element of the operator stack.

If the priority is higher than the top element of the operator stack, press the current operator into the stack, and if the priority is lower or the same than the top element of the operator stack, take out the top operator from the operator stack, take two operands from the top of the Operand stack, and then calculate. Press the calculated results into the Operand stack and continue to compare.

Def infix_evaluator (infix_expression: str)-> int:''this is the function for evaluating the infix expression: parameter infix_expression: the infix expression needs to be separated by a space' token_list = infix_expression.split () print (token_list) # operator priority dictionary pre_dict = {'*': 3Magnum charger charger 3lemagogical expression 2lemmeric expression 2 '(': 1} # operator stack operator_stack = [] # Operand stack operand_stack = [] for token in token_list: # numeric forward Operand stack print (token) # 10 or-10 if token.isdecimal () or token [1:] .isdecimal (): operand_stack.append ( Int (token)) # left parenthesis into operator stack elif token ='(': operator_stack.append (token) # encounters the right parenthesis It is necessary to pop up the operators above the left parentheses at the top of the stack elif token = =')': top = operator_stack.pop () while top! ='(': # for every operator that pops up, two operands are popped up to evaluate # Note that the order of the pop-up operands is reverse The number that pops up first is op2 op2 = operand_stack.pop () op1 = operand_stack.pop () # the value calculated is pushed back into the Operand stack # the function used here, get_value, is defined as operand_stack.append (get_value (top,op1) below Op2)) # pops up the next stack top operator top = operator_stack.pop () # encounters the operator It is necessary to evaluate elif token in'+-* /': while operator_stack and pre_ operators [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)) # Don't forget to finally put the current operator on the stack operator_stack.append (token) # after the expression traversal is complete The remaining operators in the stack also require the value while operator_stack: top = operator_stack.pop () op2 = operand_stack.pop () op1 = operand_stack.pop () operand_stack.append (get_value (top,op1,op2)) # there is only one number left in the stack This number is the final result of the entire expression print (operand_stack) print (operator_stack) return operand_stack [0] def get_value (operator: str, op1: int) Op2: int):''these are four operation functions: parameter operator: operator: parameter op1: left Operand: parameter op2: right Operand' if operator = ='+': return op1 + op2 elif operator = ='-': return op1-op2 elif operator = ='*': return op1 * op2 elif operator = '/': return op1 / op2 # try an example The result is 17.0 print (infix_evaluator ('9 + (3-1 * 2) * 3 + 10 / 2')).

The above program only uses four operation expressions for learning calculation, but the input needs to be separated by spaces. For example, 9 + (3-1 * 2) * 3 + 10 / 2 is separated into ['9','+','(','3','-','1','*','2','),'*','3','+','10','/','2'].

Later, we tried to divide 9 + (3-1-2) * 3-10-2 into ['9','+','(','3','-','1','*','2','),'*','3','+','10','/','2'].

Then I thought of the regular expression 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']

Therefore, the difficult algorithm of infix expression evaluation using stack is basically completed.

Thank you for your reading, the above is the content of "how to understand the application of stack in parenthesis matching and expression evaluation". After the study of this article, I believe you have a deeper understanding of how to understand the application of stack in parenthesis matching and expression evaluation. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.