利用栈判断括号是否匹配

素颜马尾好姑娘i 2022-06-17 05:14 217阅读 0赞

update on 20210826

## 主要思想 ##

使用栈进行匹配，但是不要把所有的字符都入栈，只需要将三种括号入栈即可，这样会简化控制逻辑。  
代码如下：

#include<stack>
    #include<iostream>
    #include<string>
    using namespace std;
    
    string str ="{(sdf{})12}";
    stack<char> sta; //一个装char 的栈  
    
    //判断temp和当前的char 是否是一对 
    //注意pair 是
    bool is_pair(char cur, char temp){
     if (cur == '}' && temp == '{') 
      return true;
     else if (cur == ']' && temp == '[') 
      return true;
     else if (cur == ')' && temp == '(') 
      return true;
     return false;  
    }
    
    
    void is_legal(string str){
     char temp ;
     for (int i = 0;i < str.length();i++){
      cout << str[i];
      if (str[i]=='{' || str[i]=='(' || str[i]=='['){
       sta.push(str[i]); 
      }
      else if (str[i]=='}' || str[i]==')' || str[i]==']'){   
       if (!sta.empty()){ //如果当前有首字符可取
        temp = sta.top(); //取首字符
        if( is_pair(str[i],temp)) {//判断二者是否是一对 
         sta.pop();
        }
        else{
         cout <<"False";
         return ;
        }
       }  
       else{
        cout <<"False";
        return ;
       }   
      }
     }
     cout << "True";
    }
    
    int main(){
     cout << str.length()<<"\n";  
     is_legal(str);
    }

\----

1.下面给出了使用C语言自定义数据机构的代码，仅供参考

/*
    1.判断表达式中的括号是否匹配 
    */
    #include <stdio.h>
    #include <string.h> 
    #define maxSize 1000
    
    typedef struct{
    	char data[maxSize];//字符串
    	int top;//栈顶指针 	
    }Stack; 
    
    void initStack(Stack &stack);//初始化栈 
    void pushStack(Stack &stack,char data);//入栈 
    int popStack(Stack &stack);//出栈 
    bool isEmpty(Stack stack);//判断栈是否为空 
    char getTopStack(Stack stack);//取头元素 
    
    int main(){
    	char str[maxSize];
    	gets(str);//输入一个字符串 
    	int i = 0;
    	Stack stack;
    	initStack(stack);//初始化栈操作 
    	for(i = 0;i<strlen(str);i++){
    		if(str[i] =='{'||str[i] =='('||str[i]=='['){//如果为其三者之一 
    			pushStack(stack,str[i]);//将str[i]入栈			
    		}
    		else{
    			if(str[i] == '}' && getTopStack(stack) == '{' ){						
    				popStack(stack);
    			}
    			else if(str[i] ==')' && getTopStack(stack) == '('){			
    				popStack(stack);
    			} 
    			else if(str[i]==']' && getTopStack(stack) == '[' ){		
    				popStack(stack);
    			}	
    		} 
    		
    	}
    	//如果栈为空，则匹配，否则不匹配 
    	if(isEmpty(stack)){
    		printf("括号匹配！\n");
    	}
    	else printf("括号不匹配！\n");
    	return 0 ;
    }
    
    //初始化栈 
    void initStack(Stack &stack){
    	stack.top = 0;//栈顶指针置为0	
    } 
    
    //进栈操作 
    void pushStack(Stack &stack,char data){
    	if(stack.top < maxSize){
    		stack.data[stack.top++] = data;
    	}
    	else return;
    }
    
    //出栈操作 
    int popStack(Stack &stack){
    	if(stack.top!=0){
    		return stack.data[--stack.top];
    	}
    	else return -1;
    }
    
    //获取栈顶元素 
    char getTopStack(Stack stack){
    	if(stack.top!=0){
    		return stack.data[stack.top-1];
    	}
    } 
    
    //判断栈是否为空 
    bool isEmpty(Stack stack){
    	if(stack.top == 0){
    		return true;
    	}
    	else return false;
    }
    
    /**测试数据
    [](){([])} 
    */