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

2. Middle order expression to suffix expression

2.1 infix expression to suffix expression

In fact, the principle of transformation is:

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

For example (S1 is the stack for storing operators, S2 is the stack for storing generated suffix expressions):

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

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

3.2 steps to implement calculator principle with suffix expression

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: