数据结构与算法详解——栈篇(附c++实现代码)

数据结构与算法详解——栈篇(附c++实现代码),第1张

目录
    • 栈的概念
    • 栈的实现
    • 完整代码
    • 时间复杂度分析
    • 栈的应用
      • 括号匹配
      • 中缀表达式求值

的概念

  栈又叫堆栈,是一种运算受限的线性表,只能在表尾进行插入或者删除,表尾这一断也称为栈顶,另一端称为栈底,插入一般称为入栈或者压栈,删除一般称为出栈。栈的特性就是“先进先出”,例如我把1,2先后压栈,出栈的时候必须先弹出2,才能弹出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 
#include 
#include 

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();
	ArrayStack(std::vector<DataType>& v);
	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);
};

template<typename DataType>
ArrayStack<DataType>::~ArrayStack() {
	delete[] array;
}

template<typename DataType>
ArrayStack<DataType>::ArrayStack(){
	make_space(capacity);
}

template<typename DataType>
ArrayStack<DataType>::ArrayStack(const ArrayStack& as) {
	make_space(as.size());
	for (int i = 0; i < _size; i++)
		array[i] = as[i];	//注意不能写成*this[i]=as[i],因为operator[]()在声明时返回值是DataType而不是DataType&,所以返回的是右值不能赋值,而这里array[i]是数组所以可以用=赋值
	_size = as.size();
	_top = _size - 1;
}

template<typename DataType>
ArrayStack<DataType>::ArrayStack(DataType a[] , int n) {
	if (a == nullptr)throw "constructor : a[]==nullptr";
	make_space(n);
	for (int i = 0; i < n; i++)
		array[i] = a[i];
	_size = n;
	_top = _size - 1;
}

template<typename DataType>
ArrayStack<DataType>::ArrayStack(std::vector<DataType>& v) {
	make_space(v.size());
	for (int i = 0; i < v.size(); i++)
		array[i] = v[i];
	_size = v.size();
	_top = _size - 1;
}

template<typename DataType>
int ArrayStack<DataType>::size() const{
	return _size;
}

template<typename DataType>
bool ArrayStack<DataType>::empty() const{
	return _size == 0;
}

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;
}

template<typename DataType>
DataType ArrayStack<DataType>::top() const{
	if (_size == 0)throw "stack has no data";
	return array[_top];
}

template<typename DataType>
DataType ArrayStack<DataType>::operator[](int index) const {
	if (index >= _size) {
		std::cerr << "index out of bound\n";
		exit(1);
	}
	return array[index];
}
template<typename DataType>
void ArrayStack<DataType>::printStack() {
	for (int i = 0; i <= _top; i++)
		std::cout << array[i] << " ";
	std::cout << "   " << "size : " << _size << std::endl;
}

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;
}
#endif

时间复杂度分析

  出栈的时间复杂度是O(1)应该没啥问题。
  来看看入栈的时间复杂度,最好的情况下是O(1),最坏的情况下是O(n),因为需要动态扩容,涉及到数据的复制。假设原始capacity=n,在入栈n次后才会需要一次扩容变为2n,再入栈n次后才会需要一次扩容变为4n,再入栈2n次后才会需要一次扩容变为8n,以此类推,均摊下去就是O(1),所以入栈的均摊时间复杂度是O(1)。

栈的应用 括号匹配

  假设给定字符串只有(),{},[]三种括号,如果字符串里的左括号都能对应右括号返回true否则返回false,注意返回false的三种情况:

  1. 类似(}这种左右括号不匹配
  2. 只有右括号而没有左括号
  3. 只有左括号而没有右括号

  这里可以用栈实现,遍历字符串,遇到左括号就入栈;遇到右括号就从出栈一个左括号,如果左右括号匹配就继续,如果不匹配或者栈空无法出栈就返回false。

#include "stack.h"
#include 
#include 

bool MatchedParis(char l, char r) {		//判断两个括号是否左右匹配
	if ((l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']'))return true;
	return false;
}

bool ExpressionMatchedParis(std::string &str) {
	ArrayStack<char> stack;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			stack.push(str[i]);
		else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
			if (stack.empty())return false;	// 2. 只有右括号而没有左括号
			char c = stack.pop();	//弹出一个左括号
			if (!MatchedParis(c, str[i]))return false;	// 1. 类似(}这种左右括号不匹配
		}
	}
	if (!stack.empty())return false;	//3. 只有左括号而没有右括号
	return true;
}

int main() {
	std::string s1 = "asd({})[asd]{";
	if (ExpressionMatchedParis(s1))
		std::cout << "true\n";
	else
		std::cout << "false\n";

	std::string s2 = "asd(})[asd]";
	if (ExpressionMatchedParis(s2))
		std::cout << "true\n";
	else
		std::cout << "false\n";
}
中缀表达式求值

  PS:中缀表达式是指运算符在操作数中间,也就是符合我们平时习惯的一种表达式,还有前缀表达式(波兰表达式),后缀表达式(逆波兰表达式),操作符分别在操作数的前面和后面,举个例子,中缀表达式1-2*3,前缀表达式 -1*23,后缀表达式 123*-
  假设表达式只有加减乘除四种运算和括号(),假设结果和中间的操作数都在int类型范围内不会溢出,输入一条中缀表达式求值,例如(34+8)*12+4/(8-6),求表达式的结果。
  这里我们用两个栈来实现,一个栈存储操作数,一个栈存储操作符。遍历表达式,遇到操作数就压入操作数栈;当遇到操作符的时候,就要与操作符栈的栈顶元素进行比较:

  1. 如果操作符优先级>栈顶元素,操作符入栈
  2. 如果操作符优先级<=栈顶元素,就从操作符栈里取栈顶的操作符,操作数栈里弹出两个操作数,进行运算,将结果压入操作数栈中,然后继续拿这个操作符和栈顶元素比较优先级,直到跳到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),可是进到括号里面后,+的优先级应该比左括号高,+才能入栈,当遇到右括号时,右括号优先级比+低,才能弹出+计算2+3。或者换个角度说,括号里的+因为括号优先级变得比普通+高了。
  这里priority是用来比较入栈后的操作符的优先级的,所以这里的括号优先级是1,只比哨兵#高(因为哨兵#必须是最低优先级的才有意义)。
  而入栈前的左括号我们单独写一个逻辑,遍历字符串遍历到左括号时,这时未入栈的左括号优先级最高,直接入栈即可。

if (priority[str[i]] > priority[ops.top()] || str[i] == '(') {
	ops.push(str[i]);
	break;
}

  5、遍历完栈里可能还有没计算完的操作符和操作数,举个例子1+2*3-2:

numops分析
1#1入栈
1# +优先级+>#,+入栈
1 2# +2入栈
1 2# + *优先级*>#,*入栈
1 2 3# + *3入栈
1 6# +遍历到减号,优先级-<*,计算2乘3,栈也弹出2、3、*,num入栈结果6
7#还是在减号这里,优先级-==+,计算1+6,栈也弹出1、6、+,num入栈结果7
7 2# -还是在减号这里,优先级->#,-入栈

  计算到这里后,还有个减号没有计算,这里可以遍历栈依次把栈中剩下的运算符计算完。也可以再加一个哨兵#,因为#比其他运算符优先级都小,所以最后加个#就能把栈中剩余的运算符计算完,逻辑也能统一成上面的操作符优先级比较的两个步骤,这里我们是使用这种方法,所以输入表达式的末尾要带个#。
  接上面最后再加个#

numops
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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址:http://outofmemory.cn/langs/914815.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-05-16
下一篇2022-05-16

随机推荐

发表评论

登录后才能评论

评论列表(0条)

    保存