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

This article mainly explains "how to understand the conversion and evaluation of prefix, suffix and infix expressions". The explanation in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian and study and learn "how to understand the conversion and evaluation of prefix, suffix and infix expressions" together!

Arithmetic, a knowledge that is neither easy to get started nor easy to master.

Last time, I introduced how to use stack to realize infix expression evaluation. If I was the title setter, of course, I would have to test prefix, suffix, and infix expressions to convert each other, and then it would become the use of stack to realize prefix and suffix expression evaluation.

Prefix, suffix, infix expression mutual conversion and its operation, can be said to be a computer exam focus.

First look at the table below:

Note: The antecedent expression and the consequent expression have no sign extension.

Infix expression to prefix expression evaluation

Rules for infix expressions to prefix expressions:

1. Invert the input string, such as "2*3/(2-1)+3*(4-1)" after inversion," )1-4(*3+)1-2(/3*2", 2. Take out the next character from the string 2.1. If it is an operand, output directly 2.2. If it is ")," push it into the stack 2.3. If it is an operator but not "(",")," loop through the following 2.3.1. If the stack is empty, push the operator to the stack and end this step. 2.3.2. If the top of the stack is ")," then this operator is pushed to the stack, ending this step. 2.3.2. If the operator has the same or higher priority as the top of the stack, the operator is pushed to the stack, ending this step. 2.3.4. Otherwise, the operator continues to pop until one of the three conditions above is met, and then the operator is pushed. 2.4 If it is "(", then the operator continues to pop the stack until it meets ")". 3. If there are more strings, go to step 2. 4. There are no unprocessed strings anymore. Output the remaining elements in the stack. 5. Invert the string again to get the final result.

After the above steps, the output is both the prefix expression obtained by the conversion.

Prefix expression calculation method: scan prefix expression from back to front, set an operand stack, if it is an operand, put it directly on the stack, if it is an operator, pop the operand corresponding to the operator from the stack for operation, and push the calculation result on the stack. Until the prefix expression is scanned from right to left, there should be only one element in the operand stack, and the value of that element is the result of the prefix expression.

The above process is implemented using a data structure stack, and the specific code is as follows

''' @Author: Runsen @WeChat: RunsenLiu @ Weixin Official Accounts: King of Python @CSDN: blog.csdn.net/weixin_44510615: github.com/MaoliRUNsen: 2020/12/17 ''' import re class Stack(): def __init__(self): self.items = [] def push(self, item): return self.items.append(item) def pop(self): return self.items.pop() def size(self): return len(self.items) def peek(self): return self.items[len(self.items) - 1] def display(self): print(self.items) def infix_to_prefix(s): prec = { '*': 3, '/': 3, '+': 2, '-': 2, '(': 4, ')': 1 } a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input ('Please enter infix expression:')) prefix = [] for x in a[::-1]: if re.match('[0-9]', x): #operand, direct output prefix.append(x) else: #If yes ")", push into stack if x == ')': s.push(x) elif x == '(': while True: i = s.pop() if i == ')': break else: prefix.append(i) else: if s.size() > 0 and prec[x]

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.