How to convert an infix expression to a suffix expression in C++

This article shows you how to convert an infix expression into a suffix expression in C++. The content is concise and easy to understand, which will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

First, the idea: it is similar to the calculation of infix expressions, except that the expression can be output without calculation.

1. Using a character array to store infix expressions for the entire line of input

two。 Then judge the character from the zero position of the character array, if it is a number, then determine whether it is followed by a number, and if so, keep scanning to form an integer.

(not considering negative numbers and decimals for the time being), finally form an integer, and then output this number (because you don't have to calculate, so you can output directly)

3. If it is a left parenthesis, go directly into the symbol stack

4. If it is an operation operator, compare priority to the top element of the symbol stack: press into the stack if high

If it is low, take out the element output at the top of the symbol stack

Next, determine that the element at the top of the symbol stack and the current operation symbol continue to compare priority, and repeat the previous steps until the stack is empty or the current symbol has a high priority.

5. If it is a right parenthesis, take out the element at the top of the symbol stack, if not the left parenthesis, output the operator taken out, and then take the element at the top of the symbol stack until the symbol in the symbol stack is left parenthesis

6. When the character array is scanned, determine whether the symbol stack is empty:

If not empty, the element at the top of the symbol stack is taken out and output to the window until the symbol stack is empty.

Second, the implementation program:

/ / suffix expression to suffix expression / / operator: +, -, *, /,% / input: you can use cin.getline (arr) Or cin.get (ch) & & ch! ='\ ninclude include / Test data: input format: (note: no Chinese operators) / / 2 + (3 + 4) * 5 shock / 16 seconds 30 include / output format: / / 2 34 + 5 * + / 16 2 30 * 4 / + # include # include / / determine whether it is the operator bool isOperator (char Ch) {if (ch = ='+'| | ch = ='-'| | ch = ='*'| | ch = ='/') return true Return false; / / otherwise return false} / / get priority int getPriority (char ch) {int level = 0; / / priority switch (ch) {case'(': level = 1; break; case'+': case'-': level = 2; break; case'*': case'/': level = 3; break; default: break } return level;} int main (int argc, const char * argv []) {/ / insert code here... Int num; char arr [250]; / / read expressions one by one until you encounter the'\ 0' std::stack op; / / stack op: storage operator while (1) {std::cin.getline (arr,250); int len, i; char c; / / c stores the operator len = (int) strlen (arr) fetched from the stack / / strlen () outputs unsigned long type, so cast to int type I = 0; while (I < len) {if (isdigit (arr [I])) {/ / if it is numeric num = 0; do {num = num * 10 + (arr [I] -'0') / / ch-48 according to the ASCAII code, the conversion relationship between characters and numbers; / / next character} while (isdigit (arr [I])); std::cout