Expression evaluation

1、 Infix expression to prefix expression （ Manual calculation ）

notes ： In the process of infix expression to prefix expression , Scan expression from right to left , As long as the operator on the right can calculate , Give priority to the one on the right . This ensures that the resulting suffix expression is unique , And it takes effect from right to left ！

2、 Calculation of prefix expression （ Computer calculation ）

 Use stack to calculate prefix expression （ The first thing out of the stack is the left operand ）

    （1）、 Scan the next element from right to left , Until all the elements are processed 
    
    （2）、 If the operand is scanned and pushed onto the stack , And back to （1）; otherwise （3）

    （3）、 If operator is scanned , Then two stack top elements pop up , Perform the corresponding operation , Push the result back to the top of the stack , And back to （1）
    
    （4）、 Cycle the above steps back and forth , Until all the elements are processed , There must be only one element in the stack , Otherwise, the prefix expression is incorrect , It's illegal 

Be careful , Because the next element is scanned from right to left to perform the operation , So the right operand is the most advanced stack , The backward is left-wing math , However, due to the characteristics of stack first in and last out , So the left operand comes out of the stack first when encountering the operator ！

3、 Infix expression to suffix expression （ Manual calculation ）

In the process of infix expression to suffix expression , Scan the scan expression from left to right , As long as the operator on the left can calculate , Give priority to the one on the left . This ensures that the resulting suffix expression is unique , And it takes effect from left to right ！

4、 The calculation of suffix expression （ Manual calculation ）

5、 Suffix expression evaluation （ Computer calculation ）

（4）、 Cycle the above steps back and forth , Until all the elements are processed , There must be only one element in the stack , Otherwise, the suffix expression is incorrect , It's illegal 

6、 Infix expression to suffix expression （ Computer calculation ）

 Initialize a stack , It is used to save operators whose operation order cannot be determined temporarily 

 Scan the elements from left to right , Till the end , There are three possible situations ：

   （1）、 Encountered operand . Add directly to the suffix expression 
   
   （2）、 Delimiter encountered 
   
           encounter “（” Add directly to the stack 
            
           encounter “）” Then pop up the operators in the stack in turn and add the suffix expression , Until it pops up “（” until （ Be careful ：“（” Is not added to the suffix expression ）, Because the current delimiter “）” It must be better than the stack top operator +、-、*、） The priority is low , Therefore, the priority is higher than “）” All operators of , Until the top element with the same priority pops up “（”
   
   （3）、 Operator encountered （ View operator stack ）
   
           If the current operator has a lower priority than the top of the stack operator , Pop up all operators in the stack with priority higher than or equal to the current operator , And add it to the suffix expression , Then press the current operator onto the stack 
          
           If the current operator has higher priority than the stack top operator , Then directly stack the current operator 
          
           If the stack top element is “（”, Then directly press the current meta operator onto the stack （ Because the current operator +、-、*、/、（ The priority of is definitely higher than the top element “） High priority ”） 
          
           if   Empty in stack , Then directly push the current operator onto the stack 
          
   （4）、 After processing all the characters according to the above method , Pop up the remaining operators in the stack in turn , And add suffix expression ！

7、 The calculation of infix expression （ While generating suffix expression , At the same time, the computer method of suffix expression is used to calculate the suffix expression ）

 First, you need to initialize two stacks , One is the operand stack , One is the operator stack 

 Scan each character in the expression from left to right 

     If the operand is scanned , Push directly into the operand stack 

     If you scan to an operator or delimiter , according to “ Infix expression to suffix expression ” The same logic is pushed into the operator stack （ But operators will pop up during , Whenever an operator pops up , You need to pop up the top elements of the two operand stacks and perform the corresponding operations , The result of the operation is pushed back to the operand stack again ）

 After scanning from left to right , If the operator stack is empty and there is only one element at the bottom of the operand stack , Then the infix expression is legal , Otherwise, the infix expression is illegal ！

8、 Algorithm implementation of infix expression （c edition ）