括号检验匹配——使用栈实现

待我称王封你为后i 2021-06-22 15:36 362阅读 0赞

# 括号检验匹配问题 #

## 问题描述 ##

假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数。

## 思路： ##

数据结构选择：栈。  
初始化一个栈。  
从第一个字符开始检索整个字符串：  
如果有`([{`，就把这个字符压入栈。  
如果遇到`)]}`：先判断栈是否为空，如果栈为空，括号匹配错误，函数返回0。如果栈不空，判断栈顶元素是否可以和响应字符匹配。如果匹配，把栈顶元素抛出，程序继续进行。如果不匹配，括号匹配错误，函数返回0。  
当字符串遍历完，如果栈内还有元素，函数返回0。如果栈为空，表示括号匹配没有错误。

## 代码： ##

#include<iostream>
    #include<stack>
    #include<queue>
    #include<stdio.h>
    #include<cstdio>
    using namespace std;
    bool correct(char* str);
    int main()
    { 
    	char s1[] = "{}[]()";
    	cout << correct(s1) << endl;
    	char s2[] = "{[()]}";
    	cout << correct(s2) << endl;
    	char s3[] = "{[()()][()()]}";
    	cout << correct(s3) << endl;
    	char s4[] = "((()))";
    	cout << correct(s4) << endl;
    	char s5[] = "{}[[]][";
    	cout << correct(s5) << endl;
    
    	return 0;
    }
    bool correct(char* str)
    { 
    	stack<char> s;
    	char* p;
    	for (p = str; *p; p++)
    	{ 
    		if (*p == '(' || *p == '[' || *p == '{')
    			s.push(*p);
    		else if (*p == ')' || *p == ']' || *p == '}')
    		{ 
    			if (s.empty() == 1)
    				return 0;
    			if (*p == ')') { 
    				if (s.top() != '(')
    					return 0;
    				else s.pop();
    			}
    			if (*p == ']') { 
    				if (s.top() != '[')
    					return 0;
    				else s.pop();
    			}
    			if (*p == '}') { 
    				if (s.top() != '{')
    					return 0;
    				else s.pop();
    			}
    		}
    	}
    	if (s.empty() == 0)
    		return 0;
    	return 1;
    }

## 简单测试： ##

做了简单的测试，结果都符合预期。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]

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

以上就是全部内容，谢谢你的阅读。

**如有纰漏，请不吝指出，不胜感激。**

如果你不沉下心来认真练习，所有的阅读都是白费的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]: /images/20210615/74d4c153ac3a486cb3f8bdfec87ec167.png