假设一个算术表达式中可以包含三种括号：园括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用

Question

假设一个算术表达式中可以包含三种括号：园括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。

Answer 1

#include<iostream>
#include<stdlib.h>
using namespace std;
#define maxsize 100

int flag = 0;
char useless;

//定义顺序表结构
typedef struct {
    string s;
    int length;
}SeqList;//不要定义成指针，否则你必须开辟空间

//定义堆栈
typedef struct {
    int top;
    char elem[maxsize];
}Stack;

//初始化顺序表
void initList(SeqList& L) {
    L.length = 0;
}

//初始化堆栈
void initStack(Stack& S) {
    S.top = -1;
}

//输入创建顺序表
void createList(SeqList& L) {
    cin >> L.s;
    //L->length = sizeof(L->s)-1;sizeof函数结果包含'\0'
    L.length = L.s.length();
}

//入栈
bool push(Stack &S,char ch) {
    if (S.top == maxsize - 1) {
        return false;
    }
    S.top++;
    S.elem[S.top] = ch;
    return true;
}

//出栈
bool pop(Stack &S, char &ch) {
    if (S.top == -1) {
        return false;
    }
    ch = S.elem[S.top];
    S.top--;
    return true;
}

bool isEmpty(Stack S){
    return S.top == -1;
}

char topElem(Stack S) {
    return S.elem[S.top];
}

void matchBracket(Stack& S, char lbracket) {
    while (S.elem[S.top] != lbracket) {
        pop(S, useless);
    }
    pop(S, useless);
    flag--;
}

//检测算法
bool checkExp(SeqList L, Stack S) {
    int i = 0;
    int count = L.length;
    //char useless;int flag = 0;
    while (count--) {
        if (L.s[i] >= '0' && L.s[i] <= '9') {//当前是数字
            i++;
            continue;
        }
        else {//当前是符号，包括运算符、左括号和右括号
            if (L.s[i] == '(' || L.s[i] == '[' || L.s[i] == '{') {
                push(S, L.s[i]);
                flag++;
            }
            else if(L.s[i] =='+' || L.s[i]=='-' || L.s[i] == '*' || L.s[i] == '/'){
                char top = topElem(S);
                if (top == '+' || top == '-' || top == '*' || top == '/') {//if(top == '(' || ....)
                    pop(S, useless);
                }
                else {
                    push(S, L.s[i]);
                }
            }
            else if(L.s[i] == ')' || L.s[i] == ']' || L.s[i] == '}'){//当前是右括号
                if (flag > 0) {
                    if (L.s[i] == ')') {
                        matchBracket(S, '(');
                    }
                    else if (L.s[i] == ']') {
                        matchBracket(S, '[');
                    }
                    else {
                        matchBracket(S, '{');
                    }
                }
                else {
                    return false;
                }
            }
            else {
                cout << "输入的字符有误" << endl;
                return false;
            }
        }
        i++;
    }
    if (isEmpty(S)) {
        return true;
    }
    else {
        char top = topElem(S);
        if (top == '+' || top == '-' || top == '*' || top == '/') {
            return true;
        }
        else {//栈顶是左括号
            return false;
        }
    }
}

//[5+(6-3)]-(2+3)]
//flag记录栈内含有左括号的个数，当flag为0但当前扫描到的字符为右括号，则匹配错误
int main() {
    SeqList l;
    Stack s;
    initList(l);
    initStack(s);
    createList(l);

    if (checkExp(l, s)) {
        cout << "yes" << endl;
    }
    else {
        cout << "no" << endl;
    }

}