栈的基本应用(二):括号及引号的匹配

要求:

编写一个程序,判断一个字符串中的左右括号及引号是否匹配。括号(英文状态下的圆括号、方括号、花括号)允许嵌套,引号(英文状态下的单引号、双引号)亦可嵌套。假定输入的字符串不超过100个字符。

思路:

使用一个括号栈,一个引号栈。当识别一个左括号时,将其入括号栈,当识别到一个右括号时,验证其是否与栈顶括号是同一种类型;当识别一个引号时,若引号栈为空或栈顶元素不与识别的引号匹配,将识别的引号入栈,否则出栈。字符串遍历完毕后,若括号栈和引号栈同时为空,则左右括号及引号匹配,反之则不匹配。

#include <bits/stdc++.h>
using namespace std;

class SeqStack
{
public:
    SeqStack(int cnt);
    bool pop(); //出栈
    bool push(char num); //压栈
    bool isFull();
    bool isEmpty();
    int getLength(); //取栈的长度
    char getTop()
    { return *(p+top); }
    void show();
    void empty()
    { bottom = top; }
    ~SeqStack()
    {
        delete [] p;
    }
private:
    int top; //栈顶位置
    int bottom; //栈底位置,此处不存放有效值
    char * p; //顺序栈数组的首地址
    int cnt; //顺序栈的最大长度
};

SeqStack::SeqStack(int cnt)
{
    p = new char[cnt+1]();
    bottom = top = 0;
    this->cnt = cnt;
}

bool SeqStack::isEmpty()
{
    if (bottom == top)
        return true;
    else
        return false;
}

bool SeqStack::isFull()
{
    if (top == cnt)
        return true;
    else
        return false;
}

int SeqStack::getLength()
{
    return top;
}

bool SeqStack::push(char newChar)
{
    if (this->isFull())
    {
        cout<<"顺序栈已满,无法压栈!"<<endl;
        return false;
    }
    top++;
    *(p+top) = newChar;
    return true;
}

bool SeqStack::pop()
{
    if (this->isEmpty())
    {
        cout<<"顺序栈为空,无法出栈!"<<endl;
        return false;
    }
    top--;
    return true;
}

void SeqStack::show()
{
    if (this->isEmpty())
    {
        cout<<"顺序栈为空,无法遍历!"<<endl;
        return;
    }
    for (int i = 1; i<=top; i++)
    {
        printf("%c ",*(p+i));
    }
    printf("\n");
}

int main()
{
    string str;
    int i;
    SeqStack stack1(50),stack2(50); //stack1为括号栈,stack2为引号栈
    cout<<"请输入需要检测的字符串:"<<endl;
    cin>>str;
    for (i = 0; i<str.length(); i++)
    {
        switch (str[i])
        {
            case '(':
            case '[':
            case '{':
                stack1.push(str[i]); //将括号前半边入栈
                break;
            case '\'':
            case '\"':
                //若栈顶已经为对应的引号(即可配对),则出栈,否则入栈
                if (stack2.getTop() == str[i] && !stack2.isEmpty())
                    stack2.pop();
                else
                    stack2.push(str[i]);
                break;
            //检测括号右半边
            case ')':
                if (stack1.getTop() == '(')
                {
                    stack1.pop();
                    break;
                }
                else
                {
                    cout<<"所输入字符串的括号或引号不匹配!"<<endl;
                    return 0;
                }
            case ']':
                if (stack1.getTop() == '[')
                {
                    stack1.pop();
                    break;
                }
                else
                {
                    cout<<"所输入字符串的括号或引号不匹配!"<<endl;
                    return 0;
                }
            case '}':
                if (stack1.getTop() == '{')
                {
                    stack1.pop();
                    break;
                }
                else
                {
                    cout<<"所输入字符串的括号或引号不匹配!"<<endl;
                    return 0;
                }
            default:
                break;
        }
    }
    if (stack1.isEmpty() && stack2.isEmpty()) //两个栈同时为空,则括号和引号匹配
        cout<<"所输入字符串的括号和引号匹配!"<<endl;
    else
        cout<<"所输入字符串的括号或引号不匹配!"<<endl;
    return 0;
}

运行多个测试实例的结果如下:






发表评论

电子邮件地址不会被公开。 必填项已用*标注