kawaii

栈的一些使用
1.括号匹配//链栈的建立及括号匹配 typedef struct LinkNode { char da...
扫描右侧二维码阅读全文
04
2021/03

栈的一些使用

1.括号匹配

//链栈的建立及括号匹配
typedef struct LinkNode { 
    char data;
    struct LinkNode *next;
} LinkNode, *LinkStack;

bool InitStack(LinkStack &Q) { //初始化链栈
    LinkNode *head = (LinkNode *) malloc(sizeof(LinkNode));
    Q = head;
    Q->next = NULL;
    return true;
}

bool isEmpty(LinkStack Q) { //是否为空
    if (Q->next == NULL)
        return true;
    else
        return false;
}

char getTop(LinkStack Q) {
    if (!isEmpty(Q))
        return Q->next->data;
    else
        return 0;
}

bool push(LinkStack &Q, char x) { //入栈
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data = x;
    s->next = Q->next;
    Q->next = s;
    return true;
}

bool pop(LinkStack &Q, char &x) { //出栈
    if (isEmpty(Q))
        return false;
    else {
        x = Q->next->data;
        Q->next = Q->next->next;
    }
    return true;
}

bool bracketCheck(char str[], int length) { //括号匹配
    LinkStack Q;
    InitStack(Q);
    for (int i = 0; i < length; i++) {
        if (str[i] == '[' || str[i] == '(' || str[i] == '{') {
            push(Q, str[i]);
        } else {
            if (isEmpty(Q))
                return false;
            char topElem;
            pop(Q, topElem);
            if (str[i] == ')' && topElem != '(')
                return false;
            if (str[i] == ']' && topElem != '[')
                return false;
            if (str[i] == '}' && topElem != '{')
                return false;
        }
    }
    return true;
}

2.中缀表达式转后缀表达式

void mid_late(LinkStack &Q, char mid[], char late[], int length) { //中缀转后缀
    int k = 0;
    char topItem; //记录栈顶元素
    for (int i = 0; i < length; i++) { //遍历表达式
        if (mid[i] >= 'A' && mid[i] <= 'Z') //是操作数,直接入式
            late[k++] = mid[i];
        else if (mid[i] == '+' || mid[i] == '-' || mid[i] == '(' || mid[i] == ')') { //若是+,-操作符或括号
            if (isEmpty(Q) || mid[i] == '(') //若栈空或是左括号,直接入栈
                push(Q, mid[i]);
            else if (getTop(Q) == '*' || getTop(Q) == '/') { //当栈顶元素是*,/时,优先级高
                while (!isEmpty(Q)) { //弹出栈中所有操作符并入后缀式
                    pop(Q, topItem);
                    late[k++] = topItem;
                }
                push(Q, mid[i]); //将操作符入栈
            } else if (getTop(Q) == '(') { //当栈顶为括号时,入栈
                push(Q, mid[i]);
            } else if (mid[i] == ')') { //当扫描到右括号,弹出自左括号始的所有元素
                while (getTop(Q) != '(') {
                    pop(Q, topItem);
                    late[k++] = topItem;
                }
                pop(Q, topItem);
            } else { //栈顶为加减符的情况
                while (!isEmpty(Q)) {
                    pop(Q, topItem);
                    late[k++] = topItem;
                }
                push(Q, mid[i]);
            }
        } else if (mid[i] == '*' || mid[i] == '/' || mid[i] == '(' || mid[i] == ')') {
            if (isEmpty(Q) || mid[i] == '(')
                push(Q, mid[i]);
            else if (getTop(Q) == '+' || getTop(Q) == '-' || getTop(Q) == '(')
                push(Q, mid[i]);
            else if (mid[i] == ')') {
                while (getTop(Q) != '(') {
                    pop(Q, topItem);
                    late[k++] = topItem;
                }
                pop(Q, topItem);
            } else {
                while (!isEmpty(Q)) {
                    pop(Q, topItem);
                    late[k++] = topItem;
                }
                push(Q, mid[i]);
            }
        }
    }
    while (!isEmpty(Q)) {
        pop(Q, topItem);
        late[k++] = topItem;
    }
}
Last modification:March 4th, 2021 at 10:25 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment