栈的应用（计算器）

发表于 更新于 分类于 ，

本文介绍了栈的三种算法，分别是括号匹配算法，中缀表达式转后缀表达式算法和后缀表达式计算算法。同时，还写了一个计算器的例子将这三种算法结合起来。

括号匹配算法

  1. 初始化一个空栈，顺序读入括号
  2. 若是右括号则与栈顶元素进行匹配（若匹配，则弹出栈顶元素并进行下一元素；若不匹配，则该序列不合法）
  3. 若是左括号，则压入栈中
  4. 若全部元素遍历完毕，栈中仍然存在元素，则该序列不合法

中缀表达式转后缀表达式算法

  1. 从左到右遍历中缀表达式的每个数字和符号
    1. 如果检测到数字，则直接加入到后缀表达式中
    2. 如果检测到运算符时：
      1. 若为 (，入栈
      2. 若为 )，则依次将栈中的运算符加入后缀表达式，直到出现 (，并从栈中删除 (
      3. 若为 +，-，*，/, 则一直将栈顶元素加入到后缀表达式中，并弹出。直到栈顶元素的优先级低于自身或遇到 (。
  2. 一直到最终输出后缀表达式为止。

后缀表达式计算算法

  1. 建立一个操作数栈 S。
  2. 从左到右读表达式，如果读到操作数就将它压入栈 S 中，如果读到运算符，则取出由栈顶向下的 2 项操作数进行运算，再将运算的结果代替原栈顶的 2 项压入栈中

计算器例子

该计算器使用 c++ 语言编写，版本要大于 11 即可编译。可以实现 0-9 以内的加减乘除。支持括号。可以判断符号优先级。

由于只是为了练习一下栈的算法，所以没有过多的错误处理和更加优秀的程序结构。

大体思路：

  1. 读入一个要计算的表达式
  2. 判断括号是否匹配，如果不匹配则返回（括号匹配算法）
  3. 将中缀表达式转换为后缀表达式（中缀表达式转后缀表达式算法）
  4. 计算后缀表达式的值（后缀表达式计算算法）
  5. 输出后缀表达式的值，跳转到步骤 1

代码实现

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

// 获取一个符号的优先级

int level(char t)
{
    if (t >= '0' && t <= '9')
    {
        return 0;
    }
    else if (t == '+' || t == '-')
    {
        return 1;
    }
    else if (t == '*' || t == '/')
    {
        return 2;
    }
    else if (t == '(')
    {
        return 3;
    }
    return 4;
}
// 判断当前的括号是否匹配
bool check(string &str)
{
    stack<char> s;
    for (auto &i : str)
    {
        if (i == '(')
        {
            s.push(i);
        }
        else if (i == ')')
        {
            // ')' 多了
            if (s.empty())
            {
                return false;
            }
            s.pop();
        }
    }
    // 如果运行完了以后，还是有没有匹配完的括号，说明不合法 '(' 多了
    if (!s.empty())
    {
        return false;
    }
    return true;
}
// 中缀转后缀
string convert(string &str)
{
    //  返回的值
    string ans;
    // 栈
    stack<char> s;
    for (auto &i : str)
    {
        switch (level(i))
        {
        case 0:
        {
            // 如果是数字
            ans.push_back(i);
            break;
        }
        case 1:
        {
            // 如果是加减
            while (!s.empty() && level(s.top()) >= 1 && level(s.top()) != 3)
            {
                ans.push_back(s.top());
                s.pop();
            }
            s.push(i);
            break;
        }
        case 2:
        {
            // 如果是乘除，算法和加减一样
            while (!s.empty() && level(s.top()) >= 2 && level(s.top()) != 3)
            {
                ans.push_back(s.top());
                s.pop();
            }
            s.push(i);
            break;
        }
        case 3:
        {
            // 如果是'('
            s.push(i);
            break;
        }
        case 4:
        {
            // 如果是')'
            while (!s.empty() && level(s.top()) != 3)
            {
                ans.push_back(s.top());
                s.pop();
            }
            // 当前的循环到'('为止，此时，'('还会在栈中，在要弹出
            s.pop();
            break;
        }
        }
    }
    while (!s.empty())
    {
        ans.push_back(s.top());
        s.pop();
    }
    return ans;
}
// 计算表达式
double compute(string &str)
{
    // 计算后缀表达式
    string con = convert(str);
    // 开两个栈，一个存放符号，一个存放数字
    stack<char> sc;   // stack_char
    stack<double> si; // stack_int
    // 遍历后缀表达式
    for (auto &i : con)
    {
        // 如果是一个数字
        if (level(i) == 0)
        {
            si.push(i - '0');
        }
        else
        {
            // 如果是一个符号
            double b = si.top();
            si.pop();
            double a = si.top();
            si.pop();
            double ans;
            // 执行相应的运算
            if (i == '+')
                ans = a + b;
            else if (i == '-')
                ans = a - b;
            else if (i == '*')
                ans = a * b;
            else
                ans = a / b;
            // 将结果压入栈中
            si.push(ans);
        }
    }
    // 运行结束以后，就只剩下一个结果
    return si.top();
}
int main()
{
    while (1)
    {
        string str;
        cin >> str;
        // 检查是否括号匹配
        if (!check(str))
        {
            cout << "当前的括号不匹配" << endl;
            continue;
        }
        // 计算结果
        cout << compute(str) << endl;
    }
    return 0;
}