catalog:

1. Overview of suffixes

2. Middle order expression to suffix expression

3. Implement the principle and steps of calculator with stack suffix expression

4. Code implementation and analysis

# 1. Overview and mutual conversion of suffixes

- Prefix expression: the operator precedes the operand.
- Infix expression (polish): first of all, the prefixes and middle suffixes are expressions. The normal expressions (2 * 4-1) + 5-6 are called infix expressions.
- Suffix expression (reverse Polish): the operator precedes the operand.

The infix expression we usually see can't be calculated directly by computer, because the computer doesn't know how to calculate, but the computer can know how to calculate the pre suffix expression. That's what a prefix expression means

Parenthesis free in prefix and suffix expressions

# 2. Middle order expression to suffix expression

###### 2.1 infix expression to suffix expression

In fact, the principle of transformation is:

Traverse each number and character from left to right in turn. If it is a number, it will be output as a part of the suffix expression. If it is a symbol, judge the priority of the stack top element. If it is a right bracket or the priority is no higher than the stack top symbol (multiplication and division take precedence over addition and subtraction), the stack top element will be output as a part of the suffix expression in turn, and then the current symbol will be input into the stack until the final suffix expression is input Out.

Several points for attention:

- Operators of the same level, such as +, the priority of the advanced + is higher than that of the later + stack
- When an element is pushed into the stack, it can only be pushed in by matching elements with lower priority than itself. Otherwise, symbols with higher priority will pop up as a part of the expression and then push into the stack. For example, the stack has two elements, the bottom of which is +, and * is on the top of +. At this time - push, because the + and *The priority of both is higher than - so both pop up to become part of the expression and stack themselves
- The left parenthesis takes precedence over all the symbols outside the parenthesis and is lower than all the symbols inside the parenthesis
- When a right bracket is pushed into the stack, all elements between it and its nearest left bracket pop up as part of the expression, and then the left bracket and right bracket cancel

###### 2.2 infix expression to prefix expression:

In fact, it's almost the same as before. There are five differences between it and the postfix expression

- Infix expression to prefix expression is scanned from right to left
- The closing parenthesis takes precedence over all the symbols outside the parenthesis and is lower than all the symbols inside the parenthesis
- When a left bracket is pushed into the stack, all elements between the nearest right bracket and the left bracket pop up as part of the expression, and then the left bracket and the right bracket cancel out
- There is another difference between infix conversion suffixes: when the top of the stack belongs to the same level operator as the new operator currently encountered, the top of the stack will be out of the stack, because it is the same level that first calculates the left; then infix conversion prefix, because it is right to left traversal, so the same level operator will not be out of the stack, because out of the stack represents the last result that first calculates the right
- The resulting expression inversion is the prefix expression we need

Take 1 + ((2 + 3) * 4) - 5 as an example:

# 3. Implement the principle and steps of calculator with stack suffix expression

###### 3.1 principle of suffix expression implementation calculator

The program initializes two stacks, one is the OPTR (operator stack), the other is the opnd (operand stack), and then scans the expression, one by one. At the same time, the infix expression we input is replaced by the suffix expression

How does the program transform while calculating? For example, 9 + (3-1) * 3, we scan from left to right, so the elements of OPTR and OPND stacks change as follows

Scanned elements | OPND stack | OPTR stack |
---|---|---|

9 | 9 | empty |

+ | 9 | + |

( | 9 | +( |

3 | 93 | +( |

- | 93 | +(- |

1 | 931 | +(- |

) | 92 | + |

* | 92 | +* |

3 | 923 | +* |

No elements to scan | 96 | + |

No elements to scan | 15 (final result) | empty |

It can be found that as long as an operator pops up, two operands will pop up in the operand stack. The first one comes out on the right and the last one comes out on the left. The operator pops up to calculate the two operands. After calculation, it will be pushed into the operand stack

###### 3.2 steps to implement calculator principle with suffix expression

Our program doesn't know whether the expression you input starts or ends, so we use ා, for example, if we want to calculate 2 + 2, we need to enter 2 + 2 # (we can press the initial #, when initializing, into the operator stack) and then return to let our program calculate. The calculation process is as follows: the program initializes two stacks, one is OPTR (operator stack), the other is opnd (operator stack), and then scans the expression, one is read in character (we regard the number and operator as characters). If the expression is not scanned (i.e. no ×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××

1. If the character is not an operator, press it into the OPND stack to read the next character

2. If the character is an operator, different processing will be done according to the priority comparison result between the top stack element of OPTR and the newly scanned character

(1) if it is less than, ch pushes into the OPTR stack and reads the next character

(2) if it is greater than, the operator at the top of the OPTR stack will pop up, and two numbers will pop up from the OPND stack for corresponding operation, and the result will be pushed into the OPND stack

(3) if it is equal to, the top element of the OPTR stack is "(" and the newly scanned character is ")", then "(" on the top of the pop-up OPTR stack is equivalent to the success of bracket matching, and then read in the next character

# 4. Code implementation and analysis

#include<stdio.h> const char oper[7] = { '+', '-', '*', '/', '(', ')', '#' }; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char SElemType; typedef int Status; typedef struct SNode { int data; struct SNode *next; } SNode, *LinkStack; //Construct an empty stack Status InitStack(LinkStack &S) { S = NULL; return OK; } //Judge whether it is an empty stack bool StackEmpty(LinkStack S) { if (!S) return true; return false; } //Return the item element of S with e Status GetTop(LinkStack &S) { if (!S) return ERROR; return S->data; } //Insert e as a new item element Status Push(LinkStack &S, SElemType e) { SNode *p = new SNode; if (!p) { return OVERFLOW; } p->data = e; p->next = S; S = p; return OK; } //Delete the item element of S and return its value with e Status Pop(LinkStack &S, SElemType &e) { SNode *p; if (!S) return ERROR; e = S->data; p = S; S = S->next; delete p; return OK; } /*Determine whether a character entered is an operator *ch Character representing input *oper The operators recognized by the system are stored in the array */ bool In(char ch) { for (int i = 0; i < 7; i++) { if (ch == oper[i]) { return true; } } return false; } /*Compare the priority of two operators *a，b Store operators to be compared in */ char Precede(char a, char b) { if ((a == '(' && b == ')') || (a == '#' && b == '#')) { return '='; } else if (a == '(' || a == '#' || b == '(' || (a == '+' || a == '-') && (b == '*' || b == '/')) { return '<'; } else return '>'; } /*Carry out the operation of two numbers *a，b Two operands to be calculated are stored in char *theta Characters representing operators in *Result returned as char */ char Operate(char a, char theta, char b) { switch (theta) { case '+': return (a - '0') + (b - '0') + 48; case '-': return (a - '0') - (b - '0') + 48; case '*': return (a - '0') * (b - '0') + 48; case '/': return (a - '0') / (b - '0') + 48; } return 0; } //Algorithm 3.22 expression evaluation char EvaluateExpression() {//Operator first algorithm for arithmetic expression evaluation, set OPTR and OPND as operator stack and operand stack respectively LinkStack OPTR, OPND; char ch, theta, a, b, x, top; InitStack(OPND); //Initializing the OPND operand stack InitStack(OPTR); //Initialize OPTR operator stack Push(OPTR, '#'); //Press the expression start character "×" into the OPTR stack scanf("%c",&ch); while (ch != '#' || (GetTop(OPTR) != '#')) //The expression has not been scanned or the top element of OPTR is not '×' { if (!In(ch)) { Push(OPND, ch); scanf("%c",&ch); } //Enter OPND stack if ch is not an operator else switch (Precede(GetTop(OPTR), ch)) //Compare the stack top element of OPTR with the priority of ch { case '<': //Stack top element low priority Push(OPTR, ch); scanf("%c",&ch); //Press the current character ch into the OPTR stack and read the next character Ch break; case '>': Pop(OPTR, theta); //Pop up the operator at the top of the OPTR stack Pop(OPND, b); Pop(OPND, a); //Two operands on top of pop-up OPND stack Push(OPND, Operate(a, theta, b)); //Push the operation result into OPND stack break; case '=': //The top element of the OPTR stack is "(" and ch is ")" Pop(OPTR, x); scanf("%c",&ch); //Pop up "(" at the top of OPTR stack and read in the next character ch break; } //switch } //while return GetTop(OPND); //OPND stack top element is the result of expression evaluation } int menu() { int c; printf("0-9 Polynomial calculation within\n" ); printf("1.calculation\n"); printf("0.sign out\n"); printf("choice:"); scanf("%d",&c); return c; } int main() { do { switch (menu()) { case 1: { printf("Please enter the expression to evaluate (both operand and result are 0-9 To the extent of#End):\n Such as 2+2# \n" ); char res = EvaluateExpression();//Algorithm 3.22 expression evaluation printf("The calculation result is%d\n",res - 48); printf("--------------------------------------\n"); } break; case 0: printf("Exit successful\n"); return 0; default: break; } } while (1); return 0; }

example: