栈的应用(括号匹配问题)

括号匹配问题是一种典型的栈思想的应用。利用栈先进后出原则，使得最里面的括号最先匹配，一次出栈匹配到最外面。代码如下：

#include <iostream>#include <stdio.h>#define MaxSize 10/* run this program using the console pauser or add your own getch, system("pause") or input loop *//**栈的应用,括号的匹配问题。 *///定义一个静态方式的栈 typedef struct{    char data[MaxSize];//静态数组存放栈元素     int top;//栈顶指针 }Stack; //初始化栈 void InitStack(Stack &S){    S.top = -1;}//判断栈是否空bool isEmpty(Stack &S){    if(S.top==-1){        return true;    }else{        return false;    }} //入栈bool PushStack(Stack &S,char x){    if(S.top==MaxSize-1){//栈满报错         return false;    }//top指针先指向最新的栈顶元素     S.data[++S.top] = x;//将值赋给栈顶元素     return true;} //出栈(x返回)bool PopStack(Stack &S,char &x){    if(S.top = -1){//栈空报错         return false;    }    x = S.data[--S.top];    return true;}  //括号匹配bool StackMatch(char str[],int length){    Stack S;//声明栈    InitStack(S);//初始化栈    for(int i=0;i<length;i++){        if(str[i]=='(' || str[i]=='[' || str[i]=='{'){            PushStack(S,str[i]);//扫描到左括号入栈         }else{            if(isEmpty(S)){                return false;            }            char topElem;            PopStack(S,topElem);//栈顶元素出栈             if(str[i]=='(' && topElem!=')'){                return false;            }            if(str[i]=='[' && topElem!=']'){                return false;            }            if(str[i]=='{' && topElem!='}'){                return false;            }        }       }    return isEmpty(S);//栈空说明匹配成功 } int main(int argc, char** argv) {    char str[] = {'('};    char str1[] = {'(',')'};    char str2[] = {'(','(','(',')',')'};    char str3[] = {'(','(',')',')',')'};    char str4[] = {')'};    /*    printf("您要匹配的括号元素是:");    for(int i=0;i<5;i++){        printf("%c",str2[i]);    }    */    bool flag = StackMatch(str2,5);     printf("\nflag=%d",flag);    return 0;}

更多相关文章

随机推荐