使用栈(stack)简单地判断表达式合法性

      栈Stack是一种常见的数据结构,常用于函数调用,表达式处理等方面,栈结构就像是一个井,push操作就是把东西扔进井里面,pop操作就是把东西捞上来,很显然,后面仍下去的东西会先被捞上来,所以我们说Stack结构是一种先进后出,后进先出的结构。

      大家可能注意到,我们写代码的时候,比较智能的编辑器都会有一些错误提示,如果我们写了“(”而没有对应的”)“,那么就会看到提示,所以这是咋做到的?其实是使用了Stack栈结构。下面我们看一下使用Stack进行验证的规则:

      做一个空栈,读取字符串,依次对每个字符进行处理,如果不是(){}等符号字符,则跳过,如果是一个起始符号例如”(“,”{“,则把字符仍入栈中,如果字符是一个结束符合,那么当栈空时报错,当栈非空时,弹出顶部元素,验证是否与当前处理的字符匹配,若匹配,处理下一个,若不匹配,产生错误。最后当字符结束时,查看栈是否为空,如果栈中依然有元素,则报错。

      看下面的代码(很简单的,耐心看一下哈):

#include <iostream>
#include <stack>
using namespace std;
bool isTrueExpression(char exp[]);//主要的验证函数
bool isMarch(char,char);
int main(){
    char exp1[]="int main(void){for(){}return 0;}";//三个待验证的表达式
    char exp2[]="int main(void){for({)}return 0;}";
    char exp3[]="int main(void{for(){}return 0;}(";
    if(isTrueExpression(exp1))  cout<<"Exp1:True"<<endl;
    if(isTrueExpression(exp2))  cout<<"Exp2:True"<<endl;
    if(isTrueExpression(exp3))  cout<<"Exp3:True"<<endl;
    return 0;
}
bool isTrueExpression(char exp[]){
    stack<char> sta;
    for(;(*exp)!='\0';){//依次对字符进行处理,直到结尾
        //cout<<"handle:"<<*exp<<endl;
        if((*exp)=='('|(*exp)=='{'|(*exp)=='['){//如果字符是( { [等起始符合,那么扔入栈中
            sta.push(*exp);
            //cout<<"push:"<<*exp<<endl;
        }else if((*exp)==')'|(*exp)=='}'|(*exp)==']'){//如果是) } ]等符合,那么继续进行验证
            if((int)sta.size()==0){//如果栈是空的,返回false
                //cout<<"return F size==0"<<endl;
                return false;
            }else if(!isMarch(sta.top(),*exp)){
             //如果盏不空,取栈顶元素进行匹配,如果匹配失败,返回false
                return false;
            }else{//匹配成功,则把栈顶元素弹出
                //cout<<"pop:"<<*exp<<endl;
                sta.pop();
            }
        }
        if(*++exp=='\0'&&(int)sta.size()!=0){//验证是否到达结尾,
            //如果到达结尾,验证Stack是否为空,如果栈非空,则返回false
            return false;
        }
    }
    return true;
}
bool isMarch(char c1,char c2){
    //cout<<"比较"<<c1<<"和"<<c2<<endl;
    if(c1=='('){
        if(c2==')') return true;
    }else if(c1=='{'){
        if(c2=='}') return true;
    }else if(c1=='['){
        if(c2==']') return true;
    }
    //cout<<"不匹配"<<endl;
    return false;
}

以上代码输出为:

Exp1:True

 

发表评论

邮箱地址不会被公开。