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

要求：

编写一个程序，判断一个字符串中的左右括号及引号是否匹配。括号（英文状态下的圆括号、方括号、花括号）允许嵌套，引号（英文状态下的单引号、双引号）亦可嵌套。假定输入的字符串不超过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;
}

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