堆栈的使用

堆栈

堆栈是一种线性的数据结构,只能在一端插入和删除
先进先出!
在C++中

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <stack>
using namespace std;

int main(){
stack<int> s;//定义栈
s.push(1);//压栈
cout<<s.top();//读取栈顶元素
s.pop();//出栈
}

经典应用

括号匹配

括号匹配
左括号压入栈
注意:字符串的使用

表达式求值

1.建立两个堆栈,一个保存数字,一个保存符号
2.在表达式的首和尾插入两个人为标记的两个优先级最低的运算符
3.遍历表达式的字符串,如果遇到数字,直接压入数字栈
4.如果遇到运算符,跟栈顶的比较优先级,如果优先级高,或者符号栈为空,则压入符号栈
5.如果遇到运算符小于或者等于栈顶运算符,则从栈顶弹出运算符,并且从数字栈弹出两个数字,进行运算,并将结果压入数字栈。再进行4步
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
#include <iostream>
#include <stdio.h>
#include <stack>
using namespace std;


int getPriority(char operation){
if (operation=='+'||operation=='-')
return 1;
else if (operation=='*'||operation=='/')
return 2;
else
return 0;
}

double calculate(char operation, double a , double b){
switch (operation){
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
}
}

int main(){
string str;
while (cin>>str){
stack<double> number_stack;
stack<char> operation_stack;
//首尾添加自定义符号
operation_stack.push('$');
str+='$';
int length = str.length();
for (int i = 0; i <length ; ++i) {
//如果是数字直接压入栈
if (isdigit(str[i])){
double number = str[i]-'0';
if (i>0&&isdigit(str[i-1])){
number = number_stack.top()*10+number;
number_stack.pop();
}
number_stack.push(number);
}
else{
char operation = str[i];
while (true){
//判断是否结束
if (operation_stack.top()=='$'&&operation=='$')
break;
//优先级高或者空栈,则入栈
if (operation_stack.empty()||getPriority(operation)>getPriority(operation_stack.top())){
operation_stack.push(operation);
break;
}
else{
char top_operation = operation_stack.top();
operation_stack.pop();
double b = number_stack.top();
number_stack.pop();
double a = number_stack.top();
number_stack.pop();
number_stack.push(calculate(top_operation,a,b));
}
}
}
}
printf("%.2f\n",number_stack.top());
}
}