温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

括号匹配算法

发布时间:2020-08-05 16:46:23 来源:网络 阅读:1511 作者:汇天下豪杰 栏目:编程语言

1、基于栈的应用

  括号匹配算法是栈的一个典型应用;所以的借用栈来实现,保存相应的信息;

  算法思想:遇到第一个字符, 判断栈空,字符入栈,其后的字符和栈顶元素进行比较,括号匹配的话,则栈顶元素出栈,否则,当前元素入栈,直到遇到0结束标志;最后根据栈空判断,空:括号匹配,否则,不匹配;

  例:([{}])是匹配的括号,为正确的;


2、代码实现

#include<iostream>
#include<stack>
using namespace std;

typedef unsigned char boolean;
#define    TRUE    1
#define FALSE    0

boolean backetMatch(char *str);
boolean backetMatch(char *str){
    stack<int> s;
    int i = 0;
    
    while(str[i]){
        if(s.empty()){
            s.push(str[i]);
        }else{
            if(s.top() == ')' || s.top() == ']' || s.top() == '}'){
                return FALSE;  //首先出现右括号的,肯定是不匹配的;
            }

            if(s.top() == '('){ //为'('的情况
                if(str[i] == ')'){
                    s.pop();
                }else{
                    s.push(str[i]);
                }
            }else if(s.top() == '['){ //为'['的情况
                if(str[i] == ']'){
                    s.pop();
                }else{
                    s.push(str[i]);
                }
            }else if(s.top() == '{'){ //为'{'的情况
                if(str[i] == '}'){
                    s.pop();
                }else{
                    s.push(str[i]);
                }
            }
        }
            i++;
    }

    if(s.empty()){
        return TRUE;
    }else{
        return FALSE;
    }
}

int main(void){
    char *str = "({[])}";
    boolean flag;

    flag = backetMatch(str);
    if(flag){
        printf("括号匹配\n");
    }else{
        printf("括号不匹配\n");
    }
    
    return 0;
}


3、结果截图

括号匹配算法




向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI