Icoding题解

题干

栈 后缀表达式计算

请使用已定义好的栈完成后缀表达式计算:
(1)如果是操作数,直接入栈
(2)如果是操作符op,连续出栈两次,得到操作数x 和 y,计算 x op y,并将结果入栈。

后缀表达式示例如下:
9 3 1 - 3 * + 10 2 / +
13 445 + 51 / 6 -
操作数、操作符之间由空格隔开,操作符有 +,-,*, /, %共 5 种符号,所有操作数都为整型。

栈的定义如下:

1
2
3
4
5
6
7
8
9
#define Stack_Size 50
typedef struct{
ElemType elem[Stack_Size];
int top;
}Stack;

bool push(Stack* S, ElemType x);
bool pop(Stack* S, ElemType *x);
void init_stack(Stack *S);

其中,栈初始化的实现为:

1
2
3
void init_stack(Stack *S){
S->top = -1;
}

需要完成的函数定义为:
int compute_reverse_polish_notation(char *str);

函数接收一个字符指针,该指针指向一个字符串形式的后缀表达式,函数返回该表达式的计算结果。

分析

  • 简要分析题干
    栈运用的一个经典问题就是计算后缀表达式,关键点在于理解后缀表达式的运算逻辑。
    运算逻辑如下:

    1. 只要是操作数,一律直接放入栈中
    2. 如果读到了运算符,出栈第一次得到y,出栈第二次得到x
    3. 务必注意,我们进行的运算是 x op y
    4. 将运算结果入栈
      同时这里还有个值得注意的地方,运算数并不是个位数,所以将非个位数的字符串转化为整数,需要一些额外的操作,同时,数字和操作符之间是有空格的,也需要注意跳过空格。
  • 应当注意的问题

    1. 字符串转化为数、运算符的方法
    2. 栈的性质
    3. 细节处理
  • 解题思路
    由函数定义可知,我们得到的仅仅是一个字符串,任务无非可以拆分成以下几步完成:

    1. 得到字符串的长度
    2. 遇到字符串数字,将其转化为整数,入栈
    3. 遇到空格,跳过空格继续读取字符串后面的内容
    4. 遇到操作符,先出栈得到y,后出栈得到x,运行x op y,运算结果入栈,继续读取后面的数字
    5. 循环以上步骤,直到字符串被完全读取
    6. 最后出栈的数就是最后的运算结果

注释代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
int compute_reverse_polish_notation(char *str) {
//获取字符串长度
int len = strlen(str);
//我们需要一个变量来储存读取到的字符串内的数字
int number = 0;
//还要有一个变量来储存我们遍历到的字符串的位置
int index = 0;

//先声明一个栈,后续会使用
Stack S;
init_stack(&S);

//这是后续进行后缀运算必需的变量
int x,y;

//循环终止条件是:一旦index等于len,就说明走完了字符串
//注意数组的最大下标是len - 1,访问第len个位置会出问题的
while (index < len) {
//第一个条件判断:是否为空格
if (str[index] == ' ') {
//如果是空格,直接选择跳过。
//index加1表示跳过当前的空格,直接进行下一轮循环
index++;
continue;
}
//第二个条件判断,index指向的字符是否是数字
//这里要特别注意,数字不止是个位数,从第一个数字开始要继续往后读取处理
else if (str[index] >= '0' && str[index] <= '9') {
//number的初始值设置为0
number = 0;
//循环终止的条件是读取到的字符是空格
while (str[index] != ' ') {
//将字符串表示的数字转化为正常的数字
//str[index] - '0'即可得到该数字的int形式
number = 10 * number + (str[index] - '0');
//继续看下一个数字
index++;
}
//已得到数字,入栈
push(&S, number);
}
//第三个条件:是操作符
else {
//以下的条件判断很容易看明白在做什么,此处不再赘述
//唯一需要强调的是,出栈的第一个数是y,第二个数是x
//我们进行的操作是 x op y
if (str[index] == '+') {
pop(&S, &y);
pop(&S, &x);
push(&S, x + y);
}
else if (str[index] == '-') {
pop(&S, &y);
pop(&S, &x);
push(&S, x - y);
}
else if (str[index] == '*') {
pop(&S, &y);
pop(&S, &x);
push(&S, x * y);
}
else if (str[index] == '/') {
pop(&S, &y);
pop(&S, &x);
push(&S, x / y);
}
else if (str[index] == '%') {
pop(&S, &y);
pop(&S, &x);
push(&S, x % y);
}

index++;
}
}

ElemType res;
pop(&S, &res);

return res;
}

完整代码

这一版的判断操作数写得更好看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int compute_reverse_polish_notation(char *str){
Stack S;
init_stack(&S);
int len;
len = strlen(str);
int i = 0;
while(i < len)
{
if (str[i] == ' ')
{
i++;
continue;
}
if (str[i] >= '0' && str[i] <= '9')
{
int number = 0;
while (i < len && (str[i] >= '0' && str[i] <= '9'))
{
number = number * 10 + (str[i] - '0');
i++;
}
push(&S, number);
}
else
{
ElemType x, y, result = 0;
pop(&S, &y);
pop(&S, &x);
if (str[i] == '+')
result = x + y;
else if(str[i] == '-')
result = x - y;
else if(str[i] == '*')
result = x * y;
else if(str[i] == '/')
result = x / y;
else if(str[i] == '%')
result = x % y;
push(&S, result);
i++;
}
}

int res;
pop(&S, &res);
return res;

}