Python data structures and algorithms in the stack in detail (3)

What are the preorder, midorder, and postorder expressions?

For arithmetic expressions like B∗C , the correct operation can be based on its form. In the B∗C example, since the multiplication sign appears between two variables, we know that we should multiply the variable B by the variable C .

Because the operator appears in the middle of two operands , such expressions are called mid-order expressions.​

Let's look at another example of a middle-order expression, A + B ∗ C. Although the operators " + " and " * " are both between operands, there is a problem: which operands do they act on respectively? Does " + " act on A and B? Does " * " act on B and C? This expression seems ambiguous.

In fact, we read and write these kinds of expressions all the time and have not encountered any problems. This is because, we know the characteristics of operators. Every operator has aprioritization . In arithmetic, theHigher-priority operators participate before lower-priority operators.. The only thing that can change the order of operations is parentheses. Multiplication and division take precedence over addition and subtraction.

While these laws are obvious to humans, computers need to know exactly which operations to perform in which order. One way to eliminate ambiguity is to writeangle bracket expression (math.) . Such expressions add a pair of parentheses to each operator. This is done by theParentheses determine the order of operations, there is no ambiguity and there is no need to memorize any prioritization rules.

For example, A+B∗C+D can be rewritten as ((A+(B∗C))+D) to show that multiplication takes precedence and then the addition expression on the left is computed. Since addition combines from left to right, A+B+C+D can be rewritten as (((A+B)+C)+D).

Now that we've learned about the principles of mid-order expressions, there are two other important expressions that may not be readily apparent, and those arePre- and Post-order Expressions。​

Take the middle-order expression A+B as an example. If you put the operator before the two operands, you getprepositional expression+AB . Similarly, if you move the operator to the end, you getbackward sequential expressionAB+ . These two expressions look a bit strange.

By changing the relative positions of the operators and operands, we get respectivelyprepositional expression cap (a poem)backward sequential expression . A preorder expression requires that all operators appear before the two operands on which it acts, and the reverse is true for a postorder expression. The following table lists some examples.

A+B∗C can be rewritten asprepositional expression + A ∗ B C 

The fact that the multiplication sign appears before B and C means that it has a higher priority than the plus sign. The plus sign appears before A and the multiplication result.

A+B∗C corresponds tobackward sequential expressionYes A B C ∗ +

The order of operations is still correctly preserved, due to the fact that the multiplication sign appears immediately after B and C, meaning that it has a higher priority than the addition sign.

With respect to preorder and postorder expressions, the order of operations does not change, even though the operators are moved before or after the operands.
​

One more example: now for the middle-order expression  (A+B)∗C。

Parentheses are used to ensure that the plus sign takes precedence over the multiplication sign. However, when A+B is written as a preorder expression, the plus sign is simply moved before the operand, i.e., +AB. the result of the addition then becomes the first operand of the multiplication sign. The multiplication sign is moved to the top of the entire expression, resulting in ∗+ABC.

Similarly, the subsequence expression A B + A B+ AB+ is guaranteed to prioritize the computation of addition. Multiplication is then computed after the result of addition is obtained. Therefore, the correct subsequence expression is AB+C∗.

Some examples of mid-order, preorder and postorder expression correspondences:

Why do we need to learn pre/post-order expressions?

In the above example of a mid-order expression becoming a pre/post-order expression, notice a very important change. In the last two expressions, where did the parentheses go? Why.Parentheses are not required for forward and backward expressions.? The answer is that the operands corresponding to the operators in both expressions are explicit. Only mid-order expressions require additional notation to remove ambiguity. The order of operations in preorder and postorder expressions is determined solely by the position of the operators.

A preorder expression is a very useful expression that converts a middle-order expression into one that can be relied on to get the result of an operation by a simple operation. For example, ( a + b ) ∗ ( c + d ) (a+b)*(c+d) (a+b)∗(c+d) is converted to ∗ + a b + c d ∗+ab+cd ∗+ab+cd. It has the advantage of being able to solve the operation of any middle-order expression with just two simple operations, in-stack and out-stack. -- "Baidu Encyclopedia's explanation of the role of preorder expressions

Conversion from mid-sequence to pre-sequence and post-sequence

So far, we have used an ineffable method to convert mid-order expressions into their corresponding preorder and postorder expressions. As we thought, there must be a generalizedarithmetic, which can be used to correctly convert expressions of arbitrary complexity.

An easy way to observe this is toalternative brackets methodbut only if you use theangle bracket expression (math.)。

As mentioned earlier, one can write A+B∗C as (A+(B∗C)) to indicate thatmultiplication sign (math.)has a higher priority than theplus sign + (math.). Further observation reveals that each pair ofbracesIt actually corresponds to aneutrosophic expression(containing the two operands and the operators between them). Observe that the subexpression (B∗C) of theright bracket. If themultiplication sign (math.)move toright bracketwhere it is located, andRemove the left bracket, you get BC∗ , which actually converts that subexpression into the correspondingbackward sequential expression. If theplus sign + (math.)is also moved to the correspondingright bracketwhere it is located, and go to theDrop the corresponding left bracketIt's a great way to get the fullbackward sequential expression。

If you move the operator toleft bracketwhere it is located, andRemove the corresponding right bracketYou'll get it.prepositional expression, as shown below. In effect, the position of the bracket pair is the final position of the operator it contains.

Therefore, it would be very difficult to combine an arbitrarily complexneutrosophic expressionconvertprepositional expressionmaybebackward sequential expression, you can start by writing itangle bracket expression (math.)Then replace the brackets withoperator (computing)Move to left parentheses (for forward expressions) or right parentheses (for backward expressions).

Converting from a middle-order expression to a back-order expression using Python

We need to develop a way to combine anyneutrosophic expressionconvertbackward sequential expressionof the algorithm. To accomplish this goal, let us further observe the conversion process.

Once again, the example A+B∗C is examined. As shown earlier, its corresponding back-order expression is ABC∗+. The operandThe relative positions of A, B, and C remain the same; only the operators change position. Look again at the operators in the middle-order expression. Looking from left to right, the first operator to appear is+ . But in a backward-ordered expression, since * has a higher priority (the parentheses in which the multiplication occurs after writing it as a full parenthesis expression are operated on first), * occurs before +. In this example, the order of operators in the middle-order expression is reversed from that of the back-order expression.

During the conversion, since the operand to the right of the operator has not yet appeared (it is not known if there is still a bracket operation to the right of the operator), the operator needs to be saved somewhere first. Also, since operators have differentprioritization, so it may be necessary to reverse the order in which they are saved. This is the case with the plus and multiplication signs in this example. Since the plus sign appears before the multiplication sign in the middle-order expression, but the multiplication sign has a higher arithmetic priority, the latter expression needs to reverse the order in which they appear. Given this inversion property, it makes sense to use a stack to hold the operators.

What happens then for (A+B)∗C? It corresponds to the postorder expression AB+C∗. Looking from left to right, the first operator to appear is+ . However, because the parentheses change the priority of the operator, when processing to * the+ has been put into the result expression.

The conversion algorithm can now be summarized: When a left parenthesis is encountered, the left parenthesis needs to be saved to indicate that a high-priority operator will be encountered next (even if the operator in the parenthesis has a lower priority, it has a higher priority because it is in parentheses); that operator needs to wait until the right parenthesis corresponding to the left parenthesis appears in order to determine where it should be in the postfixed expression after it has been converted to a postfixed expression (recall the conversion method of the full parenthesized expression); when the right parenthesis appears, that is, when the position of the bracketed operator in the subordinate expression has been determined, the left parenthesis and the other operators above the left parenthesis (which may or may not be present) can be removed from the stack. (Used for fully bracketed expressions)

Implement the conversion algorithm in code:

suppose that...neutrosophic expressionis a space-separated string of tokens. The operator tokens are +-∗/, the bracket tokens are "(((" and " ) ) )", and the operand tokens areA 、B 、C etc. The following step generates a post-ordered marker string.

Steps:

1. Create an empty opstack to hold the operators and an empty list to hold the results.

2. Use the string method split to convert the input mid-order expression into a list.

3. Scan this list of markers from left to right

3.1 If the token is an operand, add it to the end of the result list.

3.2 If the token is a left bracket, press it into the opstack.

3.3 If the token is a right parenthesis, repeatedly remove elements from the opstack until the corresponding left parenthesis is removed. Each operator removed from the stack is added to the end of the result list.

3.4 If the token is an operator, press it into the opstack stack. However, before doing so, it is necessary to remove higher priority or identical operators from the stack and add them to the end of the result list.

4. When you have finished processing the input expression, check the opstack. Add all remaining operators to the end of the result list.

To implement this algorithm in Python, we use a program calledprec dictionary to hold the priority values of the operators. The dictionary maps each operator to an integer. The priority of an operator can be determined by comparing the corresponding integers (3, 2, and 1 are used arbitrarily in this example). The left bracket has the smallest priority value. In this way, any operator compared to the left bracket is pressed onto the stack. We will also import the string module, which contains a series of predefined variables. This example uses aCharacters containing all uppercase letters (string.ascii_uppercase ) to represent all possible occurrences of operandsThe following code demonstrates the complete conversion process. The following code shows the complete conversion process.

import string
class Stack:
    def __init__(self):
         = []
    def isEmpty(self):
        return  == []
    def pop(self):
        return ()
    def push(self, item):
        (item)
    def peek(self):
        return [len() - 1]
def infixToPostfix(infixexpr):
    prec = {
        "*" : 3,
        "/" : 3,
        "+" : 2,
        "-" : 2,
        "(" : 1
        }
    opStack = Stack()  # Create the stack
    postfixList = []  # Create a list of results
    tokenList = ()  # Split the math into lists
    for token in tokenList:                   # Traversing the arithmetic
        if token in string.ascii_uppercase:   # If the current element is an operand
            (token)         # Directly into the results list
        elif token == "(":                    # If the current element is left bracketed
            (token)               # Left brackets on the stack
        elif token == ")":                    # If the current element is a right bracket
            topToken = ()          # Fetch elements from the stack
            while topToken != "(":            # The fetched element is not right bracketed Loop over
                (topToken)  # elements into the results list
                topToken = ()      # Fetch elements from the stack
        else:                                 # The elements traversed are operators
            while (not ()) and (prec[()] >= prec[token]):
                # (Stack is not empty) and (Priority of operator on top of stack is greater than or equal to current operator priority) loop:
                # Top of stack elements into result list
                (())
            # Operators on the stack
            (token)
    # Put all the remaining operators on the stack into the result list #
    while not ():
        (())
    # Returns a spliced post-order expression string
    return " ".join(postfixList)
print(infixToPostfix("A + B * C"))
# A B C * +
print(infixToPostfix("( A + B ) * ( C + D )"))
# A B + C D + *

Compute the back-order expression

A final example of a stack is the computation of a back-order expression. In this example, the stack is once again the appropriate data structure to choose. However, when scanning for a postorder expression, the need to save theoperand, rather than operators. Put another way, when encountering aoperator (computing)When it is necessary to use theThe two nearest operands to itto calculate.

To further understand the algorithm, consider the subsequence expression4 5 6 * + . When scanning the expression from left to right, one first encounters the operand4 cap (a poem)5 . We are not sure what operation to perform on them until we encounter the next symbol. Therefore, we save them all in thea wooden or bamboo pen for sheep or cattleThe product can then be accessed as and when required.

In this example, immediately following the4 and 5 The symbol that appears afterward is again aoperand. Therefore, it will be6 also presses into the stack and continues to check the symbols that follow.

Now the operator * is encountered, which means that it is necessary to set theTwo recently encountered operandsMultiplication. By performing two out-of-stack operations, the corresponding operands can be obtained, and then the multiplication operation is performed 5 ∗ 6 5*6 5 ∗ 6 (the result in this case is 30).

Next, the result is pressed onto the stack. This way, it can be used as an operand when a later operator is encountered. When the last operator has been processed, there is only one value left on the stack. This value can then be removed and returned as the result of the expression.

The process is shown in the figure:

Special attention needs to be paid:​

deal withdivisionGreat care needs to be taken when doing this. Since a backward-ordered expression only changes the position of the operator, the operands are in the same position as they would be in a middle-ordered expression. When the operands of the division sign are taken from the stack in turn, their order is reversed, so we must make sure that the order of the operands is not reversed.

Implement the process of computation of backward sequential expressions in code:​

Suppose that the postorder expression is a space-separated string of tokens. where the operator tokens are ∗ / + - * / + - ∗/+- and the operand tokens are integer values of one bit. The result is an integer.

Steps:

1. Create an empty stackoperandStack

2. Use the string methodsplit Converts the input post-order expression into a list.

3. Scan this list of markers from left to right:

(1) If the marker isoperandto convert it to ainteger (math.)(since it's currently a character) and pressing in theoperandStack a warehouse

(2) If the marker isoperator (computing)notice fromoperandStack stacktwo operands. Take out the right operand the first time and the left operand the second time. Perform the corresponding arithmetic operation and then press the result into theoperandStack in the stack.

4. When the input expression is processed, the value on the stack is the result. Return it from the stack.

To facilitate the arithmetic, we define the auxiliary functiondoMath . It accepts an operator and two operands and performs the corresponding operations.

import string

class Stack:
    def __init__(self):
         = []
    def isEmpty(self):
        return  == []
    def pop(self):
        return ()
    def push(self, item):
        (item)
    def peek(self):
        return [len() - 1]

def postfixEval(postfixExpr):
    operandStack = Stack()                             # Create a stack to hold elements
    tokenList = ()                    # Split the arithmetic string
    for token in tokenList:                            # Iterate over the elements of the equation
        if token in "0123456789":                      # If the element is an operand
            (int(token))              # Convert to integer on the stack
        else:                                          # Elements are not operands, they're operators
            operand2 = ()              # Fetch from the top of the stack Operand 2
            operand1 = ()              # Fetch from the top of the stack Operand 1
            result = doMath(token,operand1,operand2)   # Call doMath for arithmetic
            (result)                  # The result of the operation goes on the stack
    return ()                          
    # Returns an element of the stack (this unique element at the end of the traversal is the result of the whole equation)
def doMath(op,op1,op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

summarize

That's all for this post, I hope it was helpful and I hope you'll check back for more from me!