《数据结构与算法》——栈（stack）的应用总结

桃扇骨 2021-11-09 10:10 228阅读 0赞

# 《数据结构与算法》——栈（stack）的应用总结 #

由于栈和队列均为**线性存储结构**，所以栈和队列这部分内容和顺序表部分的实现极为相似，对于代码部分便不进行实现了。下面仅从三个应用方向对栈的应用进行实现。

栈在括号表达式中的应用

栈在表达式求值中的应用

栈在递归中的应用

参考文献

--------------------

## 栈在括号表达式中的应用 ##

要求：对于输入一串括号符号中进行成对匹配判断，例如：(\{\}\[\])为正确格式，(\{\}\[\]\])为错误格式。测试数据：(()()()()\}\{\[\]\})

void f1(string s ){//括号匹配算法
    /*忽略括号的级别*/
    	int i;
    	stack<char> st;
    	for( i = 0;i<s.length();i++)
    		if(s[i]=='{'||s[i]=='['||s[i]=='(')
    			st.push(s[i]);
    		else if(s[i]=='}'||s[i]==']'||s[i]==')')
    			if(st.top()==s[i]-1)
    				st.pop();
    			else
    				break;
    	if(st.empty())
    		cout<<"字符串 "<<s<<"匹配成功！"<<endl;
    	else
    		cout<<"字符串 "<<s<<"匹配失败..."<<endl<<"失败处为第"<<i+1<<"位的"<<s[i]<<endl;
    }

## 栈在表达式求值中的应用 ##

要求：对于输入的一串后缀表达式进行表达式结果的计算。测试数据：5678-\*+22/-

double f2(string s){//后缀表达式求值
    	int i;
    	double a,b=0;
    	stack<double> st;
    	for(i=0;i<s.length();i++){//
    		if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')
    			try{
    				a = st.top();st.pop();
    				b = st.top();st.pop();
    				switch (s[i]){
    					case '+' : st.push(b+a);break;
    					case '-' : st.push(b-a);break;
    					case '*' : st.push(1.0*b*a);break;
    					case '/' : st.push(1.0*b/a);break;
    				}
    			}
    			catch(exception e1){
    				break;
    			}
    				
    		else
    			st.push(s[i]);
    	}
    	if(i==s.length()){
    		a = st.top();
    		st.pop();
    		if(st.empty())
    			return a;
    		else{
    			cout<<"WRONG!!"<<endl;
    			return 0;
    		}
    	}
    }

## 栈在递归中的应用 ##

要求：以斐波那契数列为例，计算当n = 5时的结果值。

**当然直接用递归或者添加两个保存的变量进行循环会更快更便捷，这里仅仅是为了体现栈的应用，对实际执行效果来讲，不推荐这种方法。**

int f3(int num){//以斐波那契数列为例
    	if(num==0||num==1)
    		return num;
    	stack<double> st;
    	st.push(0);
    	st.push(1);
    	int temp1,temp2;
    	for(int i=2;i<=num;i++){
    		temp1 = st.top();
    		st.pop();
    		temp2 = st.top();
    		st.pop();
    		st.push(temp1);
    		st.push(temp1+temp2);
    	}
    	return st.top();
    }

## 参考文献 ##

严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.

**如有错误，还请朋友不吝指正。**