《数据结构》—— 括号匹配检验

梦里梦外; 2022-09-11 12:29 184阅读 0赞

用栈处理括号匹配问题，读取表达式，当是左括号时，压入栈；等待匹配的右括号；  
当读取到与之匹配的右括号时，把栈顶的左括号弹出；依次类推直到表达式扫描完毕。  
最后得出结论表达式是否匹配成功。

*  【分析】:  
    1、先定义、创建栈的操作(查、删、插)；  
    2、定义括号匹配算法brack，初始化栈；  
    3、设置标记性变量flag来表决循环匹配结果，1表示匹配成功，0则不匹配；  
    4、扫描表达式，判断是否符合匹配条件，是左括号就调用Push压入栈

/***链栈实现括号匹配***/
    
    #include<iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef char SElemType;
    typedef int Status;
    typedef struct SNode {
        
    	int data;
    	struct SNode *next;
    } SNode, *LinkStack;
    
    Status InitStack(LinkStack &S) {
        
    	S = NULL;
    	return OK;
    }
    bool StackEmpty(LinkStack S) {
        
    	if (!S)
    		return true;
    	return false;
    }
    Status Push(LinkStack &S, SElemType e) {
        
    	SNode *p = new SNode;
    	if (!p) {
        
    		return OVERFLOW;
    	}
    	p->data = e;
    	p->next = S;
    	S = p;
    	return OK;
    }
    Status Pop(LinkStack &S, SElemType &e) {
        
    	SNode *p;
    	if (!S)
    		return ERROR;
    	e = S->data;
    	p = S;
    	S = S->next;
    	delete p;
    	return OK;
    }
    Status GetTop(LinkStack &S) {
        
    	if (!S)
    		return ERROR;
    	return S->data;
    }
    
    //算法3.21　括号的匹配
    Status Matching() {
        //检验表达式中所含括号是否正确匹配，如果匹配，则返回true，否则返回false
    	//表达式以“#”结束
    	char ch;
    	SElemType x;
    	LinkStack S;
    	InitStack(S); //初始化空栈
    	int flag = 1; //标记匹配结果以控制循环及返回结果
    	cin >> ch; //读入第一个字符
    	while (ch != '#' && flag) //假设表达式以“#”结尾
    	{
        
    		switch (ch) {
        
    		case '[' :
    		case '(': //若是左括号，则将其压入栈
    			Push(S, ch);
    			break;
    		case ')': //若是“)”，则根据当前栈顶元素的值分情况考虑
    			if (!StackEmpty(S) && GetTop(S) == '(')
    				Pop(S, x); //若栈非空且栈顶元素是“(”，则正确匹配
    			else
    				flag = 0; //若栈空或栈顶元素不是“(”，则错误失败
    			break;
    		case ']': //若是“]”，则根据当前栈顶元素的值分情况考虑
    			if (!StackEmpty(S) && GetTop(S) == '[')
    				Pop(S, x); //若栈非空且栈顶元素是“[”，则正确匹配
    			else
    				flag = 0; //若栈空或栈顶元素不是“[”，则错误匹配
    			break;
    		} //switch
    		cin >> ch; //继续读入下一个字符
    	} //while
    	if (StackEmpty(S) && flag)
    		return true; //匹配成功
    	else
    		return false; //匹配失败
    }
    int main() {
        
    	LinkStack S;
    	cout << "请输入待匹配的表达式，以“#”结束：" << endl;
    	int flag = (int) Matching();
    	if (flag)
    		cout << "括号匹配成功！" << endl;
    	else
    		cout << "括号匹配失败！" << endl;
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/41408127dc094927bdbd20083f15a388.png