用C语言的数组写一份中缀表达式转后缀表达式的代码

中缀表达式转后缀表达式，也称为逆波兰表示法(RPN)，可以采用递归的方式解决。下面是一个简单的C语言代码示例，它使用了栈来实现转换：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TOKENS 100

typedef enum { NUMBER, OPERAND, EOF } token_type;

typedef struct {
    char *token;
    int value;
    token_type type;
} token;

void get_tokens(char *expr, token tokens[], int &i) {
    while (i < strlen(expr)) {
        if (isdigit(expr[i])) {
            int start = i;
            while (isdigit(expr[i + 1])) {
                i++;
            }
            tokens[start] = (token){.token = expr + start, .value = atoi(expr + start), .type = NUMBER};
        } else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
            tokens[i].token = expr + i;
            tokens[i].type = OPERAND;
            i++;
        } else {
            break;
        }
    }
}

void infix_to_rpn(char *infix, char *rpn, token tokens[]) {
    int in_index = 0, out_index = 0;
    stack_t *stack = create_stack(MAX_TOKENS);

    for (int i = 0; tokens[i].type != EOF; i++) {
        switch (tokens[i].type) {
        case NUMBER:
            strcpy(rpn + out_index, tokens[i].token);
            out_index += strlen(tokens[i].token) + 1;
            break;
        case OPERAND:
            push(stack, tokens[i].token);
            break;
        default:
            char op = tokens[i].token[0];
            while (!is_empty(stack) && precedence(op) <= precedence(stack_top(stack))) {
                rpn[out_index++] = ')';
                pop(stack);
            }
            push(stack, op);
            break;
        }
    }

    while (!is_empty(stack)) {
        rpn[out_index++] = ')';
        pop(stack);
    }

    // Add closing parenthesis at the end
    rpn[out_index++] = '\0';
}

// Precedence of operators
int precedence(char c) {
    switch (c) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}

// Helper functions to work with stacks
stack_t *create_stack(int size) {
    stack_t *s = malloc(sizeof(stack_t));
    s->size = size;
    s->top = -1;
    s->array = malloc(size * sizeof(void *));
    return s;
}

bool is_empty(stack_t *s) {
    return s->top == -1;
}

char pop(stack_t *s) {
    if (is_empty(s))
        return '\0';
    return s->array[++s->top];
}

void push(stack_t *s, char c) {
    s->array[++s->top] = c;
}

void print_rpn(char *rpn) {
    printf("RPN expression: %s\n", rpn);
}

int main() {
    char infix[] = "5*(7+3)";
    char rpn[MAX_TOKENS]; // Initialize a buffer for RPN output
    token tokens[MAX_TOKENS];

    int i = 0;
    get_tokens(infix, tokens, i); // Get all tokens from the input

    infix_to_rpn(infix, rpn, tokens); // Convert infix to RPN

    print_rpn(rpn);
    return 0;
}

这个程序首先定义了一些辅助结构体和函数，如栈、枚举类型等。`get_tokens`函数用于从输入字符串划分出数字和运算符，并将它们存储到`tokens`数组中。`infix_to_rpn`函数实现了核心转换过程，使用栈来处理运算符优先级。最后，在`main`函数中，我们测试了一个例子并打印出后缀表达式。