数据结构栈应用 1 括号匹配

大概是一道栈的应用的水题吧。

输入一行符号,以#结束，判断其中的括号是否匹配。遇到左括号入栈，遇到右括号出栈。如果字符串结束栈不空，输出栈内左括号对应右括号。

Question

用栈实现：输入一行符号,以#结束，判断其中的括号是否匹配。括号包括：

{ } 、 [ ] 、 ( )、  < >

如果匹配，输出 right

如果不匹配，给出错误提示。包括：

第几个符号处理时出现错误；哪几个符号失配等

Example

思路

遇到左括号入栈，遇到右括号出栈。如果字符串结束栈不空，输出栈内左括号对应右括号。

没有一遍过，因为题目中没说如果出错就不再继续处理。

Answer

指定初始maxsize=1是我某种程度上的强迫症，反正这题时间限制很宽松。

#include <iostream>
#include<cstring>
#include<string>
using namespace std;
class mystack{
private:
    char *data;
    int maxsize;
    int top;
public:
    mystack(){
        maxsize=1;
        data=new char[maxsize];
        top=-1;
    }
    bool isEmpty(){
        return top==-1;
    }
    char getTop(){
        if(top>-1){
            return data[top];
        }
        return '\0';
    }
    void pop(){
        if(top>=0){
            top--;
        }
    }
    void expand(){
        char*tmp=new char[maxsize*2];
        strncpy(tmp,data,maxsize);
        maxsize*=2;
        delete[] data;
        data=tmp;
    }
    void push(char x){
        if(top+1==maxsize){
            expand();
        }
        data[++top]=x;
    }
    ~mystack(){
        delete[] data;
    }
};
char getPar(char x){
    switch(x){
    case '{':
        return '}';
    case '[':
        return ']';
    case '(':
        return ')';
    case '<':
        return '>';
    }
    return '\0';
}
int isKH(char x){
    switch(x){
    case '{':
    case '[':
    case '(':
    case '<':
        return 1;
    case '}':
    case ']':
    case ')':
    case '>':
        return 2;
    }
    return 0;
}
int main()
{
    string tmp;
    getline(cin,tmp);
    mystack*stk=new mystack();
    bool erred=false;
    for(int i=0;i<tmp.size();i++){
        char x=tmp.at(i);
        if(x=='#'){
            if(!stk->isEmpty()){
                cout<<"loss of right character ";
                while(!stk->isEmpty()){
                    cout<<getPar(stk->getTop());
                    stk->pop();
                }
                cout<<"."<<endl;
                //erred=true;
                return 0;
            }
            if(!erred){
                cout<<"right"<<endl;
            }
            return 0;
        }
        if(isKH(x)==1){
            stk->push(x);
            continue;
        }
        if(isKH(x)==2){
            if(getPar(stk->getTop())==x){
                stk->pop();
                continue;
            }else{
                cout<<"The "<<i+1<<" character '"<<x<<"' is wrong."<<endl;
                //erred=true;
                return 0;
            }
        }
    }
    //cout << "Hello world!" << endl;
    return 0;
}

最后修改于 2019-04-25

Question

Example

思路

相关

Answer