Shulou(Shulou.com)06/01 Report--

This article will explain in detail how C++ converts infix expressions into suffix expressions. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

1. Topic description

The so-called suffix expression refers to an expression in which parentheses are no longer referenced, operands are placed after two operands, and all calculations are performed strictly from left to right in the order in which they appear (regardless of the priority of the operator).

For example, the suffix expression 3 * (5mur2) + 7 corresponds to the suffix expression: 352 murmur 7 +.

Please convert the given infix expression to a suffix expression and output it.

two。 Input and output

Enter a sample:

2 4 8 + (8 8 1) / 3

Sample output:

248mm / 88mm / 1mm / 3max +

3. Problem-solving ideas

For converting an infix expression to a suffix expression, we need to solve this problem with the following steps:

1. Initialize stacks: operator stack S1

two。 Scan the infix expression from left to right

i. If you encounter numbers, output them directly.

ii. Encountered operator:

If it is'('directly into the stack

If it is')', the elements in the symbol stack will be out of the stack and output until'(','('only out of the stack, no output

For other symbols, unstack the elements in the symbol stack and output them until you encounter a symbol or'('that has a lower priority than the current symbol. Places the current symbol on the stack.

After scanning, the remaining symbols in the stack are output in turn.

4. Sample analysis

Let's take a + b * c + (d * e + f) * g as an example to explain the conversion process of the computer.

1. Traverse the expression from left to right, first encounter a, and output it directly

Output at this time: a

Stack condition: empty

two。 Continue traversing the expression, encounter +, and when the stack is empty, put it on the stack

Output at this time: a

Stack condition: +

3. Continue to traverse the expression, encounter b, and output it directly

Output at this time: a b

Stack condition: +

4. Continue traversing the expression and encounter *, because the priority of * is higher than the + at the top of the stack, so put * on the stack

Output at this time: a b

Stack situation: + *

5. Continue to traverse the expression, encounter c, and output it directly

Output at this time: a b c

Stack situation: + *

6. Continue to traverse the expression, encounter +, because the priority of + is lower than the * at the top of the stack, the * at the top of the stack will pop up; then the + of the new element at the top of the stack has the same priority as the current +, so the + will also pop up; and then the stack is empty. Put the current + on the stack.

Output at this time: a b c * +

Stack condition: +

7. Continue to traverse the expression, encounter (, put it directly on the stack, do not encounter) will not (pop up.

The output is: a b c * +

The case of the stack is: + (

8. Continue to traverse the expression, encounter d, and output it directly

The output is: a b c * + d

The case of the stack is: + (

9. Continue to traverse the expression, encounter *, because the top of the stack is (, do not encounter) will not (pop up, so put * directly on the stack.

The output is: a b c * + d

The case of the stack is: + (*

10. Continue to traverse the expression, encounter e, and output it directly

The output is: a b c * + d e

The case of the stack is: + (*

11. Continue to traverse the expression and encounter +. Because + has a lower priority than the top of the stack, it pops up; the new top element of the stack is (, does not encounter) does not pop up (, so put + on the stack.

The output is: a b c * + d e *

The case of the stack is: + (+

twelve。 Continue to traverse the expression, encounter f, and output it directly

The output at this time is: a b c * + d e * f

The case of the stack is: + (+

13. Continue to traverse the expression, encounter), directly pop up the elements in the stack and output them until they are encountered (so far, note: (pop but not output).

The output at this time is: a b c * + d e * f +

The case of the stack is: +

14. Continue to traverse the expression and encounter *. Because the priority of * is higher than the priority of the element + at the top of the stack, it will be put directly into the stack.

The output at this time is: a b c * + d e * f +

The case of the stack is: + *

15. Continue to traverse the expression, encounter g, and output it directly.

The output is: a b c * + d e * f + g

The case of the stack is: + *

16. Continue traversing the expression, empty, traversal ends. Pop up the elements in the stack one by one.

The output is: a b c * + d e * f + g * +

The case of stack is: empty

At this point, the conversion from infix expression to suffix has been completed, and the result is a b c * + d e * f + g * +.

5. The code realizes 5.1. Priority confirmation

Int priority (char op) {int priority; if (op = ='*'| | op = ='/') priority = 2; if (op = ='+'| | op = ='-') priority = 1; if (op = ='(') priority = 0; return priority;} 5.2. Conversion function / / reference symbols improve conversion efficiency void Trans (string & str, string & str1) {stack s; int i; for (I = 0; I)

='0' & & str [I] ='a'& & str [I]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.