中缀表达式转换成后缀表达式,支持多位数以及负数的运算，使用C语言实现

中缀表达式转换成后缀表达式，可以使用栈来实现。主要思路是遍历中缀表达式，遇到数字直接输出，遇到运算符则需要进行判断，如果当前运算符的优先级小于等于栈顶运算符的优先级则需要将栈顶运算符弹出并输出，直到当前运算符的优先级大于栈顶运算符的优先级，或者遇到左括号时停止弹出。最后将当前运算符入栈。如果遇到右括号，则需要将栈中左括号之后的运算符全部弹出并输出，左括号不输出。

具体实现如下：

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

#define MAX_SIZE 100

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

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

void Push(Stack *s, char c) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack is full\n");
        exit(1);
    }
    s->data[++s->top] = c;
}

char Pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty\n");
        exit(1);
    }
    return s->data[s->top--];
}

char GetTop(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty\n");
        exit(1);
    }
    return s->data[s->top];
}

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

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

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

int main() {
    char infix[MAX_SIZE], postfix[MAX_SIZE];
    Stack s;
    int i, j, k, flag, num;

    printf("Enter infix expression: ");
    scanf("%s", infix);
    InitStack(&s);
    j = 0;
    flag = 0;
    for (i = 0; infix[i] != '\0'; i++) {
        if (isdigit(infix[i])) {
            num = 0;
            while (isdigit(infix[i])) {
                num = num * 10 + infix[i] - '0';
                i++;
            }
            if (infix[i] == '.') {
                i++;
                k = 10;
                while (isdigit(infix[i])) {
                    num = num + (infix[i] - '0') / k;
                    k *= 10;
                    i++;
                }
            }
            i--;
            if (flag) {
                num = -num;
                flag = 0;
            }
            sprintf(postfix + j, "%d ", num);
            j += snprintf(postfix + j, MAX_SIZE - j, "%d ", num);
        } else if (infix[i] == '-') {
            if (i == 0 || IsOperator(infix[i - 1])) {
                flag = 1;
                continue;
            }
            while (!IsEmpty(&s) && GetPriority(GetTop(&s)) >= GetPriority(infix[i])) {
                postfix[j++] = Pop(&s);
                postfix[j++] = ' ';
            }
            Push(&s, infix[i]);
        } else if (IsOperator(infix[i])) {
            if (infix[i] == '(') {
                Push(&s, infix[i]);
            } else if (infix[i] == ')') {
                while (GetTop(&s) != '(') {
                    postfix[j++] = Pop(&s);
                    postfix[j++] = ' ';
                }
                Pop(&s);
            } else {
                while (!IsEmpty(&s) && GetPriority(GetTop(&s)) >= GetPriority(infix[i])) {
                    postfix[j++] = Pop(&s);
                    postfix[j++] = ' ';
                }
                Push(&s, infix[i]);
            }
        } else {
            printf("Invalid character\n");
            exit(1);
        }
    }
    while (!IsEmpty(&s)) {
        postfix[j++] = Pop(&s);
        postfix[j++] = ' ';
    }
    postfix[j] = '\0';
    printf("Postfix expression: %s\n", postfix);
    return 0;
}

示例输入输出如下：

Enter infix expression: 1+2*3-(4+5)/6
Postfix expression: 1 2 3 * + 4 5 + 6 / -

Enter infix expression: -2+3*4-5/2
Postfix expression: 0 2 - 3 4 * + 5 2 / -