题解 | #中缀表达式转后缀表达式#

#include <stdio.h>
#include<malloc.h>
#include <string.h>
typedef struct Stack {
    char* val;
    int size;
    int capacity;
}Stack;

void push(Stack* stack,char val) {
    if (stack->size == stack->capacity) {
        return;
    }
    stack->val[stack->size] = val;
    stack->size++;
}

char pop(Stack* stack) {
    if (stack->size == 0) return -1;
    char val = stack->val[stack->size - 1];
    stack->size--;
    return val;
}

int empty(Stack* stack) {
    return stack->size == 0;
}

char peek(Stack* stack) {
    if (stack->size == 0) return -1;
    return stack->val[stack->size - 1];
}

int gender(char val) {
    if (val == '*' || val == '/') return 2;
    if (val == '+' || val == '-') return 1;
    return 0;
}

void solution(char* src) {
    Stack* s1 = (Stack*)malloc(sizeof(Stack));
    s1->capacity = 2000001;
    s1->val = (char*) calloc(s1->capacity,sizeof(char) );
    s1->size = 0;
    Stack* s2 = (Stack*)malloc(sizeof(Stack));
    s2->capacity = 2000001;
    s2->val = (char*) calloc(s2->capacity,sizeof(char));
    s2->size = 0;

    // 1. 符号存到s1数字存到s2
    // s1 + /
    // s2 a b c * d / + a - f b
    int len = strlen(src);
    for (int i = 0; i < len; i++) {
        if (src[i] <= 'z' && src[i] >= 'a') {
            push(s2,src[i]);
        } else {
            if (gender(src[i]) <= gender(peek(s1))) {
                while (!empty(s1) && gender(src[i]) <= gender(peek(s1))) {
                    push(s2, pop(s1));
                }
                push(s1, src[i]);
            } else {
                push(s1,src[i]);
            }
        }
    }

    while (!empty(s1)) {
        push(s2, pop(s1));
    }

    while (!empty(s2)) {
        push(s1, pop(s2));
    }

    while (!empty(s1)) {
        printf("%c", pop(s1));
    }
}

int main() {
    char* src[200001];
    while (scanf("%s", src) != EOF) { // 注意 while 处理多个 case
        solution(src);
    }
    return 0;
}