后缀表达式变中缀表达式
一、什么是后缀表达式？
稍微找了下，发现网上很少有后缀表达式的定义，更多的是举例子，但是一两个例子不能完整显示出后缀表达式的特点，如果不知道定义很难确定自己写的到底是不是后缀表达式，比如123++并不是1+2+3的后缀表达式，12+3+才是，网上很多资料没有说左结合的特点（大佬：这还要说？），左结合的特点是不变的。最后，我找到了一份比较完整的定义，包括优先级，结合性
表达式包含6种操作符: +, -, *, /, (, )
(1) 先计算括号内,后计算括号外；
(2) 在无括号或同层括号内,先进行乘除运算,后进行加减运算,即乘除运算的优先级高于加减运算的优先级；
(3) 同一优先级运算,从左向右依次进行
几个例子：
1+2+3 ——> 1 2 + 3 +
1+(2-3)*4+4/2 ——> 1 2 3 - 4* + 4 2 / +
1+(2*1-3*(5+1))*4/2+4/2 ——> 1 2 1 * 3 5 1 + * - 4 * 2 / + 4 2 / +
二、解题思路
创建两个栈suffix，wait，分别存放后缀表达式和非数字字符
对字符进行以下操作：
如果是数字，直接push进suffix；
如果是 '('，直接push进wait；
如果是 ‘)’，不进栈，将wait中的第一个 ‘(’ 之前的元素依次执行pop和push进suffix的操作，最后将第一个 ‘(’ 也pop；
如果是加减乘除，和wait栈顶元素比较优先级，
若栈顶元素优先级更高或相同，则pop并push到suffix，
继续和wait栈顶元素比较，
直到栈顶元素的优先级较小，将加减乘除符号push进wait；
将wait剩余元素依次pop并push进suffix
三、C代码
以下代码有部分是debug用的
//stack.h
1 #ifndef STACK_H
2 #define STACK_H
3
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
7 #include <stdbool.h>
8
9 #define MAXSIZE 100
10
11 typedef char ElemType;
12
13 typedef struct
14 {
15 int top;
16 char data[MAXSIZE];
17 }stack;
18
19 //init
20 //pop
21 //push
22 //gettop
23 //emptystack
24 //
25
26 stack* InitStack();
27
28 bool EmptyStack(stack* );
29
30 char PopStack(stack* );
31
32 void PushStack(stack* , char );
33
34 char GetTopStack(stack* );
35
36 #endif//STACK_H
//stack.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <stdbool.h>
5 #include "stack.h"
6
7
8
9 //init
10 //pop
11 //push
12 //gettop
13 //emptystack
14 //
15
16 stack* InitStack()
17 {
18 stack* st = (stack* )malloc(sizeof(stack));
19 st->top = -1;
20 for (int i = 0; i < MAXSIZE; i++)
21 st->data[i] = ' ';
22 return st;
23 }
24
25 bool EmptyStack(stack* st)
26 {
27 return st->top == -1;
28 }
29
30 char PopStack(stack* st)
31 {
32 return st->data[st->top--];
33 }
34
35 void PushStack(stack* st, char new_top)
36 {
37 st->data[++st->top] = new_top;
38 }
39
40 char GetTopStack(stack* st)
41 {
42 return st->data[st->top];
43 }
//main.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include "stack.h"
5
6 int main()
7 {
8 char infix[MAXSIZE], tmp;
9 printf("please input the infix expression:");
10 scanf("%s", infix);
11
12 stack *suffix=InitStack(), *wait=InitStack();
13 //printf("infix:%s
strlen:%ld
",infix,strlen(infix));
14
15 for (long int i = 0; i < strlen(infix); i++)
16 {
17 //printf("the %ld th letter: %c
",i,infix[i]);
18 if (infix[i] >= '0' && infix[i] <= '9')
19 {
20 //printf("number
");
21 PushStack(suffix, infix[i]);
22 }
23 else if (infix[i] == ')')
24 {
25 //printf(")
");
26 tmp = GetTopStack(wait);
27 while (tmp != '(')
28 {
29 PopStack(wait);
30 PushStack(suffix, tmp);
31 tmp = GetTopStack(wait);
32 }
33 PopStack(wait);
34 }
35 else if (infix[i] == '(')
36 {
37 //printf("(
");
38 PushStack(wait, infix[i]);
39 }
40 else
41 {
42 //printf("symbol
");
43 while (!EmptyStack(wait)) //相同优先级，左结合
44 {
45 tmp = GetTopStack(wait);
46 if (((infix[i] == '+' || infix[i] == '-') && (tmp == '+' || tmp == '-'))
47 || (tmp == '*' || tmp == '/')
48 )
49 {
50 PopStack(wait);
51 PushStack(suffix, tmp);
52 }
53 else
54 break;
55 }
56 PushStack(wait, infix[i]);
57 //之前的bug，结合性混乱
58 /*if (!EmptyStack(wait))
59 {
60 tmp = GetTopStack(wait);
61 if (((infix[i] == '+' || infix[i] == '-') && (tmp == '+' || tmp == '-')) //if letter is higher than wait top
62 || (tmp == '*' || tmp == '/')
63 )
64 {
65 PopStack(wait);
66 PushStack(suffix, tmp);
67 }
68 }
69 PushStack(wait, infix[i]);*/
70 }
71
72 //打印每次操作的两个队列
73 /*if (!EmptyStack(suffix))
74 {
75 printf("suffix:");
76 for (int i = 0; i <= suffix->top; i++)
77 printf("%c", suffix->data[i]);
78 printf("
");
79 }
80 if (!EmptyStack(wait))
81 {
82 printf("wait:");
83 for (int i = 0; i <= wait->top; i++)
84 printf("%c", wait->data[i]);
85 }
86 printf("
");*/
87 }
88
89 while (!EmptyStack(wait))
90 {
91 tmp = GetTopStack(wait);
92 PushStack(suffix, tmp);
93 PopStack(wait);
94 }
95 for(int i = 0; i < strlen(suffix->data); i++)
96 printf("%c", suffix->data[i]);
97 free(suffix);
98 free(wait);
99 return 0;
100 }
四、错误汇总
infix字符数组需要初始化，否则初始值是随机的，这导致使用strlen（）时出现错误。suffix、wait指针需要初始化NULL。实际上，局部变量都需要初始化，在此之前不能对变量进行操作。