用C语言写一个中缀表达式转为前缀表达式的算法

中缀表达式转前缀表达式可以通过以下步骤完成：

1. 反转中缀表达式，得到倒序表达式。

2. 将倒序表达式中的左右括号颠倒位置。

3. 通过栈的方式从左到右遍历倒序表达式，对于每个操作数，直接输出；对于每个操作符，如果当前栈为空或者栈顶为右括号，则将该操作符入栈；否则，将栈中优先级大于等于该操作符的元素全部出栈并输出，直到遇到优先级小于该操作符的元素为止，然后将该操作符入栈。

4. 遍历完倒序表达式后，如果栈非空，则将栈中所有元素出栈并输出。

下面是用 C 语言实现中缀表达式转前缀表达式的算法代码：

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

#define STACK_SIZE 100
#define EXP_SIZE 100

typedef struct {
    char data[STACK_SIZE];
    int top;
} Stack;

void init(Stack *s) {
    s->top = -1;
}

int is_empty(Stack *s) {
    return s->top == -1;
}

int is_full(Stack *s) {
    return s->top == STACK_SIZE - 1;
}

void push(Stack *s, char c) {
    if (is_full(s)) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->data[++s->top] = c;
}

char pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top--];
}

char top(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top];
}

char *reverse(char *exp) {
    int len = strlen(exp);
    char *rev = (char *) malloc(len + 1);
    for (int i = 0; i < len; i++) {
        rev[i] = exp[len - i - 1];
        if (rev[i] == '(') {
            rev[i] = ')';
        } else if (rev[i] == ')') {
            rev[i] = '(';
        }
    }
    rev[len] = '\0';
    return rev;
}

int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

int precedence(char c) {
    if (c == '^') {
        return 3;
    } else if (c == '*' || c == '/') {
        return 2;
    } else if (c == '+' || c == '-') {
        return 1;
    } else {
        return 0;
    }
}

void infix_to_prefix(char *exp) {
    char *rev = reverse(exp);
    char prefix[EXP_SIZE];
    int i = 0, j = 0;
    Stack s;
    init(&s);
    while (rev[i] != '\0') {
        if (isdigit(rev[i])) {
            prefix[j++] = rev[i];
        } else if (is_operator(rev[i])) {
            while (!is_empty(&s) && precedence(top(&s)) >= precedence(rev[i])) {
                prefix[j++] = pop(&s);
            }
            push(&s, rev[i]);
        } else if (rev[i] == ')') {
            push(&s, rev[i]);
        } else if (rev[i] == '(') {
            while (top(&s) != ')') {
                prefix[j++] = pop(&s);
            }
            pop(&s);
        }
        i++;
    }
    while (!is_empty(&s)) {
        prefix[j++] = pop(&s);
    }
    prefix[j] = '\0';
    printf("Prefix expression: %s\n", reverse(prefix));
    free(rev);
}

int main() {
    char exp[EXP_SIZE];
    printf("Enter infix expression: ");
    scanf("%s", exp);
    infix_to_prefix(exp);
    return 0;
}