C++中栈有关知识的理解

谁借莪１个温暖的怀抱￠ 2023-05-21 10:18 61阅读 0赞

### 文章目录 ###

*  一、栈有关的基础知识
 *  二、栈的应用
 *   *  1、括号匹配
     *  2、括号匹配
     *  3、括号匹配，输出不匹配的括号

# 一、栈有关的基础知识 #

**1、对栈的理解**  
栈，是一种存储受限的线性数据结构，在存储和访问数据时只能够访问栈的一端，即栈是一种先进后出的数据结构。  
**2、如何定义一个栈**

*  使用栈时，需要在头文件中添加 \#include < stack>

#include<stack>
    stack<int> s;//定义一个存储整型数据的栈

**3、栈的基本操作**

stack<int> a;
    a.push(1);//向栈顶a中插入元素
    a.top();//读取栈a的栈顶元素
    a.pop();//将栈a的栈顶元素出栈
    a.empty();//判断栈是否为空，若为空则返回true,否则返回false;
    a.size();//返回栈a中元素的个数

# 二、栈的应用 #

## 1、括号匹配 ##

**输入：**  
由括号构成的字符串，包含”（“、”）“、”\[“和”\]“  
**输出**  
如果匹配输出YES，否则输出NO。  
**输入样例**

[([][]())]

**输出样例**

YES

**Code**

/*
    编写一个算法判断表达式中的括号是否正确配对 
    */
    #include<iostream>
    #include<stack> 
    #include<string>
    using namespace std;
    int main(){
        
    	//判断由( ) [ ]构成的字符串是否匹配
    	string s;
    	stack<char> c;
    	bool flag=true;
    	while(cin>>s){
        
    		int len=s.size();
    		//将左半括号入栈
    		for(int i=0;i<len;i++){
        
    				if(s[i]=='('||s[i]=='['){
        
    					c.push(s[i]);
    				} 
    				else if(!c.empty()){
        
    					char c1=c.top();//取栈顶元素 
    					if((s[i]==']'&&c1=='[')||(s[i]==')'&&c1=='(')){
        
    						c.pop();//出栈 
    						continue;
    					}
    					else{
        //不匹配 
    						break;
    					}
    					
    				}
    				else{
         
    					flag=false;
    					break;
    				}
    			}
    		if(c.empty()&&flag==true){
        
    			cout<<"YES"<<endl;
    		}
    		else{
        
    			cout<<"NO"<<endl;
    		}
    	} 
    	return 0;
    }

## 2、括号匹配 ##

题意描述： 在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。包括有大括号\{\}，中括号\[\]，小括号()，尖括号<>等。 对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号。例如，\{\[()\]\}，\{()\},\{ \{\}\}为一个合法的表达式，而(\[\{\}\])，\{(\[\])\},\[\{<>\}\]都是非法的。  
**输入描述:**  
文件的第一行为一个整数n（1≤n≤100），接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。  
**输出描述**:  
在输出文件中有N行，其中第I行对应第I个表达式的合法性，合法输出YES，非法输出NO。  
**输入样例**

5
    {
        [(<>)]}
    [()]
    <>()[]{
        }
    [{
        }]
    {
        ()}

**输出样例**

YES
    YES
    YES
    NO
    YES

**Code**

/*
    判断括号是否匹配
    1、每一对括号，必须先左边括号，然后右边括号
    2、如果有多个括号，则每种类型的左括号和右括号的个数必须相等
    3、对于多重括号，从外到内的括号嵌套顺序为大括号-中括号-小括号-尖括号 
    */ 
    #include<iostream>
    #include<stack>
    #include<string>
    using namespace std;
    int main(){
        
    	int t,flag;
    	string s;
    	cin>>t;
    	stack<char> c;
    	while(t--){
        
    		flag=1;
    		cin>>s;
    		int len=s.size();
    		//按顺序{} [] () <> 
    		for(int i=0;i<len;i++){
        
    			if(c.empty()){
        
    				if(s[i]=='{'||s[i]=='['||s[i]=='<'||s[i]=='('){
        
    					c.push(s[i]);
    				}
    			}
    			else if((s[i]=='{')&&(c.top()=='{'||c.empty())){
        
    				c.push(s[i]);
    			}
    			else if(s[i]=='['&&(c.top()=='['||c.top()=='{'||c.empty())){
        
    				c.push(s[i]);
    			}
    			else if(s[i]=='('&&(c.top()=='['||c.top()=='{'||c.top()=='('||c.empty())){
        
    				c.push(s[i]);
    			}
    			else if(s[i]=='<'&&(c.top()=='['||c.top()=='{'||c.top()=='('||c.top()=='<'||c.empty())){
        
    				c.push(s[i]);
    			}
    			else if(s[i]=='{'||s[i]=='['||s[i]=='<'||s[i]=='('){
        
    				flag=0;
    				break;
    			}
    			else if(!c.empty()){
        
    				char c1=c.top();
    				if((s[i]=='}'&&c1=='{')||(s[i]==']'&&c1=='[')||(s[i]==')'&&c1=='(')||(s[i]=='>'&&c1=='<')){
        
    					c.pop();//出栈 
    					continue;
    				}
    				else{
        
    					flag=0;
    					break;
    				}
    			}
    			else{
        
    				flag=0;
    				break;
    			}
    		}
    		if(flag==1&&c.empty()){
        
    			cout<<"YES"<<endl;
    		}
    		else{
        
    			cout<<"NO"<<endl;
    			//清空栈中的元素 
    			int l=c.size();
    			for(int i=0;i<l;i++){
        
    				c.pop();
    			}
    		}
    	}
    	return 0;
    }

## 3、括号匹配，输出不匹配的括号 ##

在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用" " 标 注 , 不 能 匹 配 的 右 括 号 用 " ? " 标 注 。 ∗ ∗ 输 入 描 述 : ∗ ∗ 输 入 包 括 多 组 数 据 ， 每 组 数 据 一 行 ， 包 含 一 个 字 符 串 ， 只 包 含 左 右 括 号 和 大 小 写 字 母 ， 字 符 串 长 度 不 超 过 100 。 注 意 ： c i n . g e t l i n e ( s t r , 100 ) 最 多 只 能 输 入 99 个 字 符 ！ ∗ ∗ 输 出 描 述 : ∗ ∗ 对 每 组 输 出 数 据 ， 输 出 两 行 ， 第 一 行 包 含 原 始 输 入 字 符 ， 第 二 行 由 " "标注,不能匹配的右括号用"?"标注。 \*\*输入描述:\*\* 输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。 注意：cin.getline(str,100)最多只能输入99个字符！ \*\*输出描述:\*\* 对每组输出数据，输出两行，第一行包含原始输入字符，第二行由" "标注,不能匹配的右括号用"?"标注。∗∗输入描述:∗∗输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。注意：cin.getline(str,100)最多只能输入99个字符！∗∗输出描述:∗∗对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"","?“和空格组成，”$“和”?"表示与之对应的左括号和右括号不能匹配。  
**输入样例**

bge)))))))))
    ((IIII))))))
    ()()()()(uuu
    ))))UUUU((()

**输出样例\#:**

bge)))))))))
       ?????????
    ((IIII))))))
            ????
    ()()()()(uuu
            $   
    ))))UUUU((()
    ????    $$

**Code**

/*
    输入一个字符串，将不匹配的括号输出
    思路：
    1、第一次遍历输入字符串：是左括号，则入栈，同时将标记数组的相应位置置为空格
    是右括号，则检测栈是否为空，不为空，则判断有对应的左括号，将标记数组的相应位置置为空格,同时出栈；
    为空，则没有对应的左括号，标记数组置 ？
    2、第二次遍历输入字符串：是右括号，则入栈
    是左括号，则检测栈是否为空，不为空，则判断有对应的右括号，同时出栈；
    为空，则没有对应的左括号，标记数组置 $。						
    */ 
    #include<iostream>
    #include<string>
    #include<cstring>
    #include<stack>
    using namespace std;
    char a[110]; 
    int main(){
        
    	string str;
    	while(cin>>str){
         
    		int len=str.size();
    		stack<char> s1;
    		//第一次遍历，判断右括号是否与最括号相匹配，将不匹配的右括号的位置置为？ 
    		for(int i=0;i<len;i++){
        
    			if(str[i]=='('){
        
    				s1.push(str[i]);//将其入栈
    				a[i]=' '; 
    			}
    			else if(str[i]==')'){
        
    				if(s1.empty()){
        //不匹配 
    					a[i]='?';	
    				}
    				else{
        
    					s1.pop();
    					a[i]=' ';
    				}
    			}
    			else{
        //为大小写字母 
    				a[i]=' ';
    			}
    		}
    		
    		for(int i=0;i<s1.size();i++){
        
    			s1.pop();
    		} 
    		//第二次遍历，判断左括号是否与右括号相匹配，将不匹配的左括号位置置为$ 
    		stack<char> s2;	
    		for(int i=len-1;i>=0;i--){
        
    			if(str[i]==')'){
        
    				s2.push(str[i]);
    			}
    			else if(str[i]=='('){
        
    				if(s2.empty()){
        
    					a[i]='$';
    				}
    				else{
        
    					s2.pop();
    				}
    			}
    		}
    		for(int i=0;i<s2.size();i++){
        
    			s2.pop();
    		} 
    		//输出 
    		cout<<str<<endl;
    		for(int i=0;i<len;i++){
        
    			cout<<a[i];
    		} 
    		cout<<endl;
    	}
    	return 0;
    }