加载中...
avatar

栈的应用

前言

   之前的一篇博客更新了用C++语言实现栈,原文在这哟😘,C/C++实现链式栈和线性栈

   今天更新一篇栈的应用(PS:使用的是C++库里面的栈),所以要加入头文件#include <stack>

进制转换

描述

   在计算机中存储的数据都是二进制,所以往往需要把十进制数据转换成二进制,转换的过程实际就是除2取余数,这其中我们可以看到最先求得余数实际是个位数,书写一个数据的时候都是先书写高位的数据,而后依次到个位。这正好利用栈先进后出的原理。

基本思想

   将待转换数取余得到的数push进栈,并且待转换数/= 进制数,直到待转换数 = 0,最后将栈依次输出并且pop出栈。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//进制转化
void BinaryConversion(int num, int transform) {
char Letter[26];
for (int i = 0; i < 26; i++)
Letter[i] = 'A' + i;
stack<int> Binary;

//计算转化结构
while (num) {
Binary.push(num % transform);
num /= transform;
}

//输出结果
int len = Binary.size();
for (int i = 0; i < len && !Binary.empty(); i++) {
int p = Binary.top();
if (p < 10)
cout << p;
else
cout << Letter[p - 10];
Binary.pop();
}
}

运行结果

括号匹配

括号匹配的四种情况

  1. 左右括号匹配正确
  2. 左右括号匹配错误
  3. 左括号多于右括号
  4. 右括号多于左括号

   但是云开在这里偷了个懒,只实了一种括号的匹配,所以没有第二种情况:2. 左右括号匹配错误😜

基本思想

  1. 扫描带匹配的字符串,当遇到三种类型的左括号('{'、'('、'[')时候让该括号进栈;
  2. 当扫描到某一种类型的右括号时,出栈;
  3. 若字符串当前为的右括号而栈已经空,则右括号多于左括号;
  4. 字符串循环扫描结束时,若堆栈非空,则说明左括号多于右括号;
  5. 否则,括号配对正确。

代码实现

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
//括号匹配
bool ParenthesisMatching(char c, string str) {
char c0;
if (c == '(')
c0 = ')';
else if (c == '{')
c0 = '}';
else
c0 = ']';

stack<char> Matching;

int len = str.length();
for (int i = 0; i < len; i++) {
if (str[i] == c)
Matching.push(c);
if (str[i] == c0) {
if (Matching.empty())
return false;
else
Matching.pop();
}
}
return Matching.empty();
}

运行结果

简单表达式求值

基本思想

  1. 扫描字符串,如果字符为数字,进数字栈

  2. 当扫描到某一种类型的右括号时,出栈;

  3. 若字符串当前为的右括号而栈已经空,则右括号多于左括号;

  4. 为操作符,操作符栈为空时,操作符进栈;

  5. 为操作符,操作符栈非空时,栈顶操作符优先级小,操作符进栈;

  6. 为操作符,操作符栈非空时,栈顶操作符优先级大:

    ​ 连续两次取数字栈(num1 ,num2)的数据出栈;

    ​ 将num2和num1按操作符栈顶的运算法则运算;

    ​ 得到的结果进数字栈,扫描的操作符进操作符栈;

  7. 扫描完后,若操作符栈非空,则重复一遍步骤四的计算方法。

辅助函数

优先级判断

1
2
3
4
5
6
7
8
//优先级判断
int priori(char c) {
if (c == '*' || c == '/')
return 2;
if (c == '+' || c == '-')
return 1;
return 0;
}

判断是数字还是操作符

1
2
3
4
5
6
7
8
/*
* 判断是数字还是操作符
* 数字返回:true
* 操作符返回:false
*/
bool is_num(char c) {
return !(c == '+' || c == '-' || c == '*' || c == '/');
}

运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* c:操作符
* num1,num2:操作数
* 返回的是num2 c num1 的值
*/
double calculation(char c, double num2, double num1) {
if (c == '*')
return num2 * num1;
if (c == '/')
return num2 / num1;
if (c == '+')
return num2 + num1;
if (c == '-')
return num2 - num1;
return 0;
}

主函数

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
//简单表达式求值
void ExpressionEvaluation(string str) {
stack<char> operate;
stack<double> num;
int len = str.length();

int n = 0;
for (int i = 0; i < len; i++) {
//为数字时
if (is_num(str[i])) {
n = 10 * n + str[i] - '0';
if (!is_num(str[i + 1]) || str[i + 1] == '\0') {
num.push(n);
n = 0;
}
}
//为操作符时
else {
//操作符栈非空
if (!operate.empty()) {
char temp = operate.top();
//栈顶操作符优先级大
if (priori(temp) >= priori(str[i])) {
//取数据
double n1 = num.top();
num.pop();
double n2 = num.top();
num.pop();
//运算并进数字栈
num.push(calculation(temp, n2, n1));

operate.pop();
operate.push(str[i]);
} else
operate.push(str[i]);
} else
operate.push(str[i]);
}
}
while(!operate.empty()){
char t=operate.top();operate.pop();
double t1=num.top();num.pop();
double t2=num.top();num.pop();
num.push(calculation(t,t2,t1));
}
cout<<num.top()<<endl;
}

运行结果

小结

博客完整的源码已经上push到了github和gitee了哟😜

Github源码

Gitee源码

文章作者: 云开、见月明
文章链接: https://chenyunxin.cn/posts/198006710.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 云开の博客
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论