Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/8.栈和队列的应用.md

8.1 括号问题

#include <stdio.h>

#define MaxSize 50
typedef char ElemType;
typedef struct SqStack {
    ElemType string[MaxSize];
    int top;
} SqStack;

bool InitStack(SqStack &sqStack) {
    sqStack.top = -1;
    return true;
}

bool EmptyStack(SqStack sqStack) {
    if (sqStack.top == -1) {
        return true;
    } else {
        return false;
    }
}

bool Push(SqStack &sqStack, ElemType x) {
    if (sqStack.top == MaxSize - 1) {
        return false;
    }
    sqStack.string[++sqStack.top] = x;
    return true;
}

bool Pop(SqStack &sqStack, ElemType &x) {
    if (sqStack.top == -1) {
        return false;
    }
    x = sqStack.string[sqStack.top--];
    return true;
}

bool GetTop(SqStack &sqStack, ElemType &x) {
    if (sqStack.top == -1) {
        return false;
    }
    x = sqStack.string[sqStack.top];
    return true;
}

//核心算法的代码实现
bool BracketCheck(const char str[], int length) {
    SqStack stack;
    InitStack(stack);
    for (int i = 0; i < length; ++i) {
        char c = str[i];
        if (c == '(' || c == '[' || c == '{') {
            Push(stack, c);
        } else {
            if (EmptyStack(stack)) {
                return false;
            }
            char topChar;
            Pop(stack, topChar);
            if (c == ')' && topChar != '(') {
                return false;
            }
            if (c == ']' && topChar != '[') {
                return false;
            }
            if (c == '}' && topChar != '{') {
                return false;
            }
        }
    }
    return EmptyStack(stack);
}

int main() {
    char string[] = "((([]{}{()})))";
    int length = sizeof(string) / sizeof(char) - 1;
    printf("待处理括号组: %s, 长度位为%d\n", string, length);
    bool result = BracketCheck(string, length);
    printf("结果为 %d", result);
    return 0;
}

8.2 中缀表达式转后缀表达式

#include<cstdio>

#define MaxSize 50
typedef char ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

void initStack(SqStack &S) {
    S.top = -1;   //初始化栈顶指针
}

bool StackEmpty(SqStack S) {
    if (S.top == -1)   //栈空
        return true;
    else
        return false;  //栈不空
}

bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1)      //栈满 不能执行入栈操作
        return false;
    S.top++;                      //指针先加1，再入栈
    S.data[S.top] = x;
    return true;
}

bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1)              //栈空 不能执行出栈操作
        return false;
    x = S.data[S.top];            //先出栈 指针再减1
    S.top--;
    return true;
}

bool GetPop(SqStack S, ElemType &x) {
    if (S.top == -1)            //栈空报错
        return false;
    x = S.data[S.top];          //用x存储栈顶元素
    return true;
}

int main() {
    SqStack S;
    initStack(S);

    ElemType InfixExpression[] = "((A+B)-C)-(E/F)";
    char PostfixExpression[50];    //在字符数组最后添加'\0',作为结束标志
    int PostfixIndex = 0;
    ElemType *pInfix = InfixExpression;

    ElemType str_temp = 0;
    while (*pInfix != '\0') {
        if (*pInfix == '*' || *pInfix == '/' || *pInfix == '+' || *pInfix == '-') {
            if (*pInfix == '*' || *pInfix == '/') {
                while (true) {
                    GetPop(S, str_temp);
                    if (str_temp == '(' || StackEmpty(S)) {
                        break;
                    }
                    Pop(S, str_temp);
                    PostfixExpression[PostfixIndex] = str_temp;
                    PostfixIndex++;
                }
                Push(S, *pInfix);
                pInfix++;
            } else {
                while (true) {
                    GetPop(S, str_temp);
                    if (str_temp == '*' || str_temp == '/' || str_temp == '(' || StackEmpty(S)) {
                        break;
                    }
                    Pop(S, str_temp);
                    PostfixExpression[PostfixIndex] = str_temp;
                    PostfixIndex++;
                }
                Push(S, *pInfix);
                pInfix++;
            }
        } else if (*pInfix == '(') {
            Push(S, *pInfix);
            pInfix++;
        } else if (*pInfix == ')') {
            while (true) {
                Pop(S, str_temp);
                if (str_temp == '(') {
                    break;
                }
                PostfixExpression[PostfixIndex] = str_temp;
                PostfixIndex++;
            }
            pInfix++;
        } else {
            PostfixExpression[PostfixIndex] = *pInfix;
            PostfixIndex++;
            pInfix++;
        }

    }

    while (!StackEmpty(S)) {
        Pop(S, str_temp);
        PostfixExpression[PostfixIndex] = str_temp;
        PostfixIndex++;
    }

    PostfixExpression[PostfixIndex] = '\0';         //在字符数组后加'\0',作为结束标志
    printf("中缀表达式为：%s", InfixExpression);
    printf("\n");
    printf("后缀表达式为：%s", PostfixExpression);
}