栈的应用——1. 括号匹配问题

image.png

解题心得：

• 栈：只允许在一端进行插入或删除操作的线性表。
• 算法：若我们按照从左到右的顺序遍历字符串，并将遇到的所有左括号都放入堆栈中等待匹配；若在遍历过程中遇到一个右括号，由于按照从左到右的顺序遍历字符串，若此时堆栈非空，那么栈顶左括号即为其匹配的左括号；相反，若堆栈为空，则表示在其之前不存在未被匹配的左括号，匹配失败。

/*
)(rttyy())sss)(
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>




int main(){

    char str[101],ans[101];
    while(scanf("%s",str)!=EOF){

        int i;
        int len=strlen(str),top=0,stackl[101]={0};
        for(i=0;i<len;i++){
            if(str[i]==')'){
                if(top>0){
                    top--;
                    ans[i]=' ';
                }
                else{
                    ans[i]='?';
                }
            }
            else if(str[i]=='('){
                        stackl[top]=i;
                        top++;
                        ans[i]=' ';
                    }
            else{
                    ans[i]=' ';

            }
        }
        while(top!=0){
            top--;
            ans[stackl[top]]='$';
        }
        printf("%s\n",str);
        for(i=0;i<len;i++){
            printf("%c",ans[i]);
        }
        printf("\n");

    }

    return 0;

}

如果觉得有用的话，就点个赞再走吧^_^