- 栈的概念
- 栈的实现
- 完整代码
- 时间复杂度分析
- 栈的应用
- 括号匹配
- 中缀表达式求值
栈又叫堆栈，是一种运算受限的线性表，只能在表尾进行插入或者删除，表尾这一断也称为栈顶，另一端称为栈底，插入一般称为入栈或者压栈，删除一般称为出栈。栈的特性就是“先进先出”，例如我把1，2先后压栈，出栈的时候必须先d出2，才能d出1。
注意：堆栈就是栈，而不是指堆和栈两种数据结构，还有， *** 作系统内存中的堆栈和数据结构中的堆栈是两回事。
栈可以用数组或者链表实现，用数组实现的称为顺序栈，用链表实现的称为链式栈，这里我实现的是顺序栈，主要的 *** 作就是入栈和出栈，注意顺序栈还要支持动态扩容，而链表天然支持动态扩容所以链式栈不用考虑动态扩容。
template<typename DataType>
class stack {
public:
virtual int size() const= 0; //返回元素个数
virtual bool empty() const= 0; //栈是否为空
virtual void push(DataType data) = 0; //入栈
virtual DataType pop() = 0; //出栈
virtual DataType top() const= 0; //返回栈顶元素
};
template<typename DataType>
class ArrayStack : public stack<DataType> { //注意这里stack也要有DataType
private:
DataType* array=nullptr;
int _size = 0; //实际存储的元素个数
int capacity = 32; //申请的空间大小
int _top = -1; //栈顶
public:
ArrayStack();
ArrayStack(const ArrayStack& as);
ArrayStack(DataType a[] , int n);
ArrayStack(std::vector<DataType>& v);
~ArrayStack();
int size() const;
bool empty() const;
void push(DataType data) ;
DataType pop();
DataType top() const;
DataType operator[](int index) const; //返回值是DataType，所以s[n]只能访问不能修改，后面const让const stack对象也能有一个访问的版本
void printStack();
private:
void make_space(int n); //扩容
};
这里定义了一个基类stack并用纯虚函数声明了一些必须实现的接口，有子类继承了stack就必须实现这几个接口。operator[]的重载可有可无，但是如果有返回值只能是DataType而不能是DataType&。
template<typename DataType>
void ArrayStack<DataType>::make_space(int n) {
if (array == nullptr)
array = new DataType[capacity];
if (capacity > n)
return;
while (capacity < n)
capacity <<= 1;
std::cout << "capacity : "<<capacity << std::endl;
DataType *tmp = new DataType[capacity];
for (int i = 0; i <= _top; i++)
tmp[i] = array[i];
delete[] array;
array = tmp;
}
先来看看扩容的函数，代码应该比较清晰，如果已经申请的容量capacity>要申请的容量n就直接返回，否则capacity就一直左移一位（乘2）直到大于等于n，然后重新申请capacity大小的空间，把旧空间的元素复制过去，然后释放旧空间。
template<typename DataType>
void ArrayStack<DataType>::push(DataType data) {
make_space(_size + 1);
array[++_top] = data;
++_size;
}
template<typename DataType>
DataType ArrayStack<DataType>::pop() {
if (_size == 0)
throw "stack is empty, no data to pop";
DataType data = array[_top--];
--_size;
return data;
}
入栈和出栈的逻辑也比较简单，需要注意入栈时需要判断是否需要扩容，出栈时需要判断栈是否为空。
完整代码#ifndef STACK_H
#define STACK_H
#include 出栈的时间复杂度是O(1)应该没啥问题。
来看看入栈的时间复杂度，最好的情况下是O(1)，最坏的情况下是O(n)，因为需要动态扩容，涉及到数据的复制。假设原始capacity=n，在入栈n次后才会需要一次扩容变为2n，再入栈n次后才会需要一次扩容变为4n，再入栈2n次后才会需要一次扩容变为8n，以此类推，均摊下去就是O(1)，所以入栈的均摊时间复杂度是O(1)。
假设给定字符串只有(),{},[]三种括号，如果字符串里的左括号都能对应右括号返回true否则返回false，注意返回false的三种情况：
- 类似(}这种左右括号不匹配
- 只有右括号而没有左括号
- 只有左括号而没有右括号
这里可以用栈实现，遍历字符串，遇到左括号就入栈；遇到右括号就从出栈一个左括号，如果左右括号匹配就继续，如果不匹配或者栈空无法出栈就返回false。
#include "stack.h"
#include PS:中缀表达式是指运算符在 *** 作数中间，也就是符合我们平时习惯的一种表达式，还有前缀表达式（波兰表达式），后缀表达式（逆波兰表达式）， *** 作符分别在 *** 作数的前面和后面，举个例子，中缀表达式1-2*3，前缀表达式 -1*23，后缀表达式 123*-
假设表达式只有加减乘除四种运算和括号()，假设结果和中间的 *** 作数都在int类型范围内不会溢出，输入一条中缀表达式求值，例如(34+8)*12+4/(8-6)，求表达式的结果。
这里我们用两个栈来实现，一个栈存储 *** 作数，一个栈存储 *** 作符。遍历表达式，遇到 *** 作数就压入 *** 作数栈；当遇到 *** 作符的时候，就要与 *** 作符栈的栈顶元素进行比较：
- 如果 *** 作符优先级>栈顶元素， *** 作符入栈
- 如果 *** 作符优先级<=栈顶元素，就从操作符栈里取栈顶的操作符，操作数栈里弹出两个操作数，进行运算，将结果压入操作数栈中，然后继续拿这个操作符和栈顶元素比较优先级，直到跳到1这种情况将这个操作符入栈。
实际实现起来还是有一些细节要处理的：
1、 *** 作数可能是负数：-38+(-8/4)，所以要先对表达式进行预处理，把在负数前添加一个0，变成 0-38+(0-8/4)。
void preprocess(std::string &str) {
for (int i = 0; i < str.length(); i++)
if (str[i] == '-') {
if (i == 0 || str[i - 1] == '(') { //第一个数是负数，或者带括号的负数
str.insert(i, 1, '0'); //在位置i前插入1个'0'
++i; //注意因为在i前插入一个'0'，str长度会变，i还要再自加一次
}
}
}
2、 *** 作数可能不止是一位，可能是多位比如24，但是我们遍历是一个一个字符遍历的，所以这里处理多位的数字，如果这一位是数字，那就判断下一位是否是数字，如果是那就这一位*10+下一位，循环直到下一位不是数字：
if (isNum(str[i])) {
int n = str[i] - '0';
while ((i + 1) < str.length() && isNum(str[i + 1])) {
n = n * 10 + (str[i + 1] - '0');
++i;
}
std::cout << "n: " << n << std::endl;
num.push(n);
continue;
}
3、其实上面两步的步骤还不完善，比如一开始 *** 作符栈是空时，无法取栈顶元素，因此我们要打个补丁，加多一个判断当栈空时直接插入 *** 作符。但是这里我们直接使用一个哨兵’#‘，在遍历字符串时栈就不会空，就不需要加这个补丁，逻辑就能统一成上面的 *** 作符比较优先级思路。所以在代码中，我们创建了 *** 作符栈后，第一个压入的元素是’#'。
ArrayStack<char> ops;
ops.push('#');
4、如何写比较优先级的代码？我们可以把优先级定义在一个map中，然后遍历到 *** 作符时在map里找到优先级大小就可以直接进行比较。
std::map<char, int> priority;
void setPriority() {
priority['#'] = 0;
priority['('] = 1;
priority[')'] = 1;
priority['+'] = 2;
priority['-'] = 2;
priority['*'] = 3;
priority['/'] = 3;
}
#的优先级最小应该没有问题。可是括号的优先级不是应该是最高的吗？这里需要注意的是左括号(是有两个优先级的，入栈前是4，入栈后是1。为什么呢？
入栈前也就是在表达式中的优先级，和我们平时的计算一样，括号是优先级最高的，最先计算的。
入栈后，也就是我们要开始计算括号内的表达式了，这个时候我们单独只看括号及括号内的表达式时，括号的优先级是最低的。
举个例子：1+(2+3)，在整个表达式中括号(的优先级是最高的，要先算括号内的表达式(2+3)，可是进到括号里面后，+的优先级应该比左括号高，+才能入栈，当遇到右括号时，右括号优先级比+低，才能d出+计算2+3。或者换个角度说，括号里的+因为括号优先级变得比普通+高了。
这里priority是用来比较入栈后的 *** 作符的优先级的，所以这里的括号优先级是1，只比哨兵#高（因为哨兵#必须是最低优先级的才有意义）。
而入栈前的左括号我们单独写一个逻辑，遍历字符串遍历到左括号时，这时未入栈的左括号优先级最高，直接入栈即可。
if (priority[str[i]] > priority[ops.top()] || str[i] == '(') {
ops.push(str[i]);
break;
}
5、遍历完栈里可能还有没计算完的 *** 作符和 *** 作数，举个例子1+2*3-2:
| num | ops | 分析 |
|---|---|---|
| 1 | # | 1入栈 |
| 1 | # + | 优先级+>#，+入栈 |
| 1 2 | # + | 2入栈 |
| 1 2 | # + * | 优先级*>#，*入栈 |
| 1 2 3 | # + * | 3入栈 |
| 1 6 | # + | 遍历到减号，优先级-<*，计算2乘3，栈也弹出2、3、*，num入栈结果6 |
| 7 | # | 还是在减号这里，优先级-==+，计算1+6，栈也d出1、6、+，num入栈结果7 |
| 7 2 | # - | 还是在减号这里，优先级->#，-入栈 |
计算到这里后，还有个减号没有计算，这里可以遍历栈依次把栈中剩下的运算符计算完。也可以再加一个哨兵#，因为#比其他运算符优先级都小，所以最后加个#就能把栈中剩余的运算符计算完，逻辑也能统一成上面的 *** 作符优先级比较的两个步骤，这里我们是使用这种方法，所以输入表达式的末尾要带个#。
接上面最后再加个#
| num | ops | |
|---|---|---|
| 7 2 | # - | 最后加个# |
| 5 | # | 因为优先级#<-，所以计算7-2，并弹出7,2，-，结果5入栈，最后结果就存在num的栈顶 |
最后来看完整代码：
std::map<char, int> priority;
void setPriority() {
priority['#'] = 0;
priority['('] = 1;
priority[')'] = 1;
priority['+'] = 2;
priority['-'] = 2;
priority['*'] = 3;
priority['/'] = 3;
}
void preprocess(std::string &str) {
for (int i = 0; i < str.length(); i++)
if (str[i] == '-') {
if (i == 0 || str[i - 1] == '(') { //第一个数是负数，或者带括号的负数
str.insert(i, 1, '0'); //在位置i前插入1个'0'
++i; //注意因为在i前插入一个'0'，str长度会变，i还要再自加一次
}
}
}
bool isNum(char c) {
if (c >= '0' && c <= '9')return true;
return false;
}
int ExpressionEvaluate(std::string &str) {
preprocess(str); //处理负数的情况
setPriority();
ArrayStack<int> num;
ArrayStack<char> ops;
ops.push('#');
int left, right, result;
for (int i = 0; i < str.length(); i++) {
if (isNum(str[i])) {
int n = str[i] - '0';
while ((i + 1) < str.length() && isNum(str[i + 1])) {
n = n * 10 + (str[i + 1] - '0');
++i;
}
num.push(n);
continue;
}
else if(priority.count(str[i])!=0){
while (1) { //注意这里要用while
if (priority[str[i]] > priority[ops.top()] || str[i] == '(') {
ops.push(str[i]);
break;
}
else {
if (ops.top() == '#')
break;
if (ops.top() == '(') {
ops.pop();
break;
}
right = num.top();
num.pop();
left = num.top();
num.pop();
switch (ops.top())
{
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
if (right == 0)
std::cout << "除数为0\n";
result = left / right;
break;
}
num.push(result);
ops.pop();
}
}
}
else {
std::cout << "非法表达式" << std::endl;
}
}
return num.top();
}
int main() {
std::string s1 = "24+(6-3)*10/3#";
std::cout << ExpressionEvaluate(s1)<<std::endl;
std::string s2 = "-24+(-6-3*2)*10/3#";
std::cout << ExpressionEvaluate(s2) << std::endl;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）