对任意给定的一个中缀算术表达式,输出等价的后缀形式,并计算结果。C语言

在C语言中，将中缀算术表达式转换成后缀（也称为逆波兰或RPN）并计算其结果的过程通常涉及到两个步骤：先转换成后缀表达式，然后使用栈来求值。

1. **转换成后缀表达式**:
使用双端队列（deque）的数据结构，遍历中缀表达式的每个字符。对于数字，直接入队；对于操作符，比较它的优先级和队首的操作符，如果当前操作符优先级高就出队并入队，否则继续比较。遇到左括号就入队，遇到右括号则一直出队直到遇到左括号为止。

2. **计算后缀表达式**:
双端队列中剩下的就是后缀表达式的元素。从队头开始，依次取出元素，如果遇到数字，就把它压入结果栈；如果遇到运算符，就弹出栈顶的两个数做运算，结果压回栈中。最后栈顶的数即为最终的结果。

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

int precedence(char op) {
    // 根据实际的算术运算符优先级设置
    return (op == '+' || op == '-') ? 1 : 2;
}

bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

void infixToPostfix(char* exp) {
    int len = strlen(exp);
    char stack[len + 1];
    int top = -1;

    for (int i = 0; i < len; ++i) {
        if (isdigit(exp[i])) {
            stack[++top] = exp[i];
        } else if (isOperator(exp[i]) && top != -1) {
            while (top > -1 && isOperator(stack[top]) && precedence(stack[top]) >= precedence(exp[i])) {
                printf("%c", stack[top]);
                --top;
            }
            stack[++top] = exp[i];
        } else if (exp[i] == '(') {
            stack[++top] = exp[i];
        } else if (exp[i] == ')') {
            while (stack[top] != '(') {
                printf("%c", stack[top]);
                --top;
            }
            --top;
        }
    }
    while (top != -1) {
        printf("%c", stack[top]);
        --top;
    }
}

int evalPostfix(char* exp) {
    int stack[100], top = -1;
    for (char c : exp) {
        if (isdigit(c)) {
            stack[++top] = c - '0'; // 转换成整数
        } else {
            int b = stack[top--], a = stack[top--];
            switch (c) {
                case '+': stack[top++] = a + b; break;
                case '-': stack[top++] = a - b; break;
                case '*': stack[top++] = a * b; break;
                case '/': stack[top++] = a / b; break;
            }
        }
    }
    return stack[top]; // 返回结果
}

int main() {
    char* expression = "A+B*C/(D-E)";
    printf("后缀表达式: ");
    infixToPostfix(expression);
    printf("\n计算结果: %d\n", evalPostfix(expression));
    return 0;
}