栈和队列的应用

数制转换

将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下：
1729776263668

代码如下：（这里我们省略了对于栈实现的代码若需要查看栈的内部代码请看：栈和队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main(){
    SqStack s;
    InitStack(&s);
    int N,r;
    cin >> N >>r;
    while(N>0)
    {
        Push(&s,N%r);
        N/=r;
    }
    cout << "N的r进制为：";
    while(!StackEmpty(s))
    {
        int e;
        Pop(&s,&e);
        cout << e ;
    }
    cout <<endl;
    return 0;
}

运行结果如下：

1729776979500

由于没有做高于10进制数的对于字母的映射，所以该程序最多只能支持转为比10更低的进制。

括弧匹配检验

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［］（））或［（［ ］［ ］）］等为正确的匹配，［（ ]）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。

代码如下：

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
int main(){
    SqStack s;
    InitStack(&s);
    char brackets[100];
    cin >> brackets;
    int i = 0;
    while(brackets[i] == '[' || brackets[i] == '(' || brackets[i] == ']' || brackets[i] == ')')
    {
        if(brackets[i] == '[' || brackets[i] == '(' )
        {
            Push(&s,brackets[i]);
        }
        else
        {  
            char tmp;
            if(StackEmpty(s))
            {
                cout << "不匹配！" << endl;
                break;
            }
            Pop(&s,&tmp);
            if(brackets[i] == ']' && tmp == '(')
            {
                cout << "不匹配！" << endl;
                break;
            }
            else if(brackets[i] == ')' && tmp == '[')
            {
                cout << "不匹配！" << endl;
                break;
            }
        }
        i++;
    }
    if(!StackEmpty(s))
    {
        cout << "不匹配！" << endl;
    }
    if(brackets[i] == '\0')
    {
        cout << "匹配成功！" << endl;
    }
    return 0;
}

运行结果如下：

1729778764481

1729778773529

博主不一定保证一定正确。

三种表达式

虽说是三种表达式，但是本篇只讲解中缀表达式和后缀表达式。本blog展示的代码都只能计算单个数字的表达式。

后缀表达式

运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。

1729779125031

计算后缀表达式，代码如下：

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
int main(){
    SqStack s;
    InitStack(&s);
    char str[100];
    cin.getline(str, 100); 
    int i = 0;
    while(str[i] != '\0')
    {
        if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
        {
            int x,y,res;
            Pop(&s,&y),Pop(&s,&x);
            if(str[i] == '+')
                res = x+y;
            else if(str[i] == '-')
                res = x-y;
            else if(str[i] == '*')
                res = x*y;
            else if(str[i] == '/')
                res = x/y;
            Push(&s,res);
        }
        else if(str[i] >= '0' && str[i] <= '9')
        {
            Push(&s,str[i]-'0');
        }
        i++;
    }
    int e;
    Pop(&s,&e);
    cout << "计算结果为："<< e <<endl;
    return 0;
}

中缀表达式转后缀表达式

1729909708239

对于这种没有括号的中缀表达式，我们给出以下解法：

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 main(){
    SqStack s;
    char str[100],e;
    cin.getline(str,100);
    InitStack(&s);
    Push(&s,'#');
    int i = 0;
    while(str[i] != '\0')
    {
        char tmp = str[i];
        if(tmp <= '9' && tmp >= '0')
        {
            cout << tmp;
        }
        else if(tmp == '+' || tmp == '-' || tmp == '*' || tmp == '/')
        {
            GetTop(s,&e);
            if(tmp == '*' ||tmp == '/')
            {   
                while(e != '#' && e!= '+' && e!='-')
                {
                    Pop(&s,&e);
                    cout <<e;
                    GetTop(s,&e);
                }
            }
            if(tmp == '+' ||tmp == '-')
            { 
                while(e != '#')
                {
                    Pop(&s,&e);
                    cout <<e;
                    GetTop(s,&e);
                }
            }
            Push(&s,tmp);
        }
        i++;
    }
    GetTop(s,&e);
    while(e != '#')
    {
        Pop(&s,&e);
        cout <<e;
        GetTop(s,&e);
    }
    return 0;   
}

我们遵守以下几点运算规则：

  1. 通过栈来暂存运算符
  2. 设表达式的结束符为#，所以提前预设栈底元素为‘#’
  3. 当前字符若是数字，直接打印出来
  4. 若当前为运算符，则需要输出栈中所存的所有优先级大于等于它的运算符
  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
int main(){
    SqStack s;
    char str[100],e;
    cin.getline(str,100);
    InitStack(&s);
    Push(&s,'#');
    int i = 0;
    while(str[i] != '\0')
    {
        char tmp = str[i];
        GetTop(s,&e);
        if(tmp <= '9' && tmp >= '0')
        {
            cout << tmp;
        }
        else if(tmp == '+' || tmp == '-' || tmp == '*' || tmp == '/' || tmp == '(')
        {
            if(tmp == '*' ||tmp == '/')
            {   
                while(e != '#' && e!= '+' && e!='-' && e != '(')
                {
                    Pop(&s,&e);
                    cout <<e;
                    GetTop(s,&e);
                }
            }
            if(tmp == '+' ||tmp == '-')
            { 
                while(e != '#' && e != '(')
                {
                    Pop(&s,&e);
                    cout <<e;
                    GetTop(s,&e);
                }
            }
            Push(&s,tmp);
        }
        else if(tmp == ')')
        {
            while(1)
            {
                Pop(&s,&e);
                if(e == '(')
                    break;
                cout <<e;
            }
        }
        else if(tmp == '#')
        {
            while(e != '#')
            {
                Pop(&s,&e);
                if(e == '#')
                    break;
                cout <<e;
            }
        }
        i++;
    }
    return 0;   
}

我们只需要增加一处if用来处理读到’)’时的反应，再将’(‘作为出栈时的一个触底条件即可。

中缀表达式求值

前面我们已经学会了中缀表达式转后缀表达式，那么对于中缀表达式求值，其实我们只需要替换一部分代码，就可以直接得到中缀表达式求值的代码

  1. 将所有打印数字的代码替代为将数字压入数字栈
  2. 将所有打印运算符号的代码改为从栈中出栈两个数据做原本打印符号的运算再将结果入栈
  3. 最后我们输出栈顶元素就是运算的结果

我们就得到以下代码：

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
int main(){
    SqStack s,n;
    InitStack(&s);
    InitStack(&n);
    char str[100],e;
    cin.getline(str,100);
    Push(&s,'#');
    int i = 0;
    while(str[i] != '\0')
    {
        char tmp = str[i];
        GetTop(s,&e);
        if(tmp <= '9' && tmp >= '0')
        {
            Push(&n,tmp-'0');
        }
        else if(tmp == '+' || tmp == '-' || tmp == '*' || tmp == '/' || tmp == '(')
        {
            if(tmp == '*' ||tmp == '/')
            {   
                while(e != '#' && e!= '+' && e!='-' && e != '(')
                {
                    Pop(&s,&e);
                    char n1,n2;
                    Pop(&n,&n1),Pop(&n,&n2);
                    if(e == '*')
                    {
                        n1 = n1 * n2;
                    }
                    else if(e == '/')
                    { 
                        n1 = n2/n1;
                    }
                    Push(&n,n1);
                    GetTop(s,&e);
                }
            }
            if(tmp == '+' ||tmp == '-')
            { 
                while(e != '#' && e != '(')
                {
                    Pop(&s,&e);
                    char n1,n2;
                    Pop(&n,&n1),Pop(&n,&n2);
                    if(e == '*')
                    {
                        n1 = n1 * n2;
                    }
                    else if(e == '/')
                    { 
                        n1 = n2/n1;
                    }
                    else if(e == '+')
                    {
                        n1 = n1 + n2;
                    }
                    else if(e == '-')
                    {
                        n1 = n2 -n1;
                    }
                    Push(&n,n1); 
                    GetTop(s,&e);
                }
            }
            Push(&s,tmp);
        }
        else if(tmp == ')')
        {
            while(1)
            {
                Pop(&s,&e);
                if(e == '(')
                    break;
                char n1,n2;
                Pop(&n,&n1),Pop(&n,&n2);
                if(e == '*')
                {
                    n1 = n1 * n2;
                }
                else if(e == '/')
                { 
                    n1 = n2/n1;
                }
                else if(e == '+')
                {
                    n1 = n1 + n2;
                }
                else if(e == '-')
                {
                    n1 = n2 -n1;
                }
                Push(&n,n1);
            }
        }
        else if(tmp == '#')
        {
            while(e != '#')
            {
                Pop(&s,&e);
                if(e == '#')
                    break;
                char n1,n2;
                Pop(&n,&n1),Pop(&n,&n2);
                if(e == '*')
                {
                    n1 = n1 * n2;
                }
                else if(e == '/')
                { 
                    n1 = n2/n1;
                }
                else if(e == '+')
                {
                    n1 = n1 + n2;
                }
                else if(e == '-')
                {
                    n1 = n2 -n1;
                }
                Push(&n,n1);
            }
        }
        i++;
    }
    char v;
    Pop(&n,&v);
    cout << int(v) << endl;
    return 0;   
}
笔记
#数据结构
栈和队列的应用
http://blog.ulna520.com/2024/10/24/栈和队列的应用_20241024_212203/
Veröffentlicht am
October 24, 2024
Urheberrechtshinweis