C语言实现中缀表达式的计算

在C语言中，中缀表达式通常是非数值类型的，为了将其转换并计算，我们需要先将其转换为后缀表达式（也称为逆波兰表示法），然后利用栈来求解。以下是基本步骤：

1. **词法分析**：将原始字符串按操作符、运算数顺序拆分，存储到符号栈和操作数队列。

2. **扫描输入**：遍历输入字符串，遇到数字就压入操作数队列；遇到左括号则继续处理，遇到右括号时，将符号栈顶的操作符依次弹出，直到遇到左括号为止，并将这些操作符和当前操作数组成一个新的表达式。

3. **解析**：当扫描到操作符时，如果操作数队列非空，则从队列取出两个操作数，进行相应的运算（如加减乘除等），并将结果推回操作数队列，然后继续处理下一个操作符。如果操作数队列为空，直接将该操作符压入符号栈。

4. **处理完整表达式**：最后，如果符号栈非空，需要将剩余的操作符与操作数结合，因为可能存在未匹配的左括号。

5. **计算后缀表达式**：当符号栈为空时，从操作数队列依次读取元素并进行计算，得到最终结果。

下面是一个简单的C函数示例，实现了上述过程：

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

// 函数定义
int getPrecedence(char op);
void evaluatePostfix(char *postfix);

int main() {
    char input[] = "2 + 3 * ( 4 - 5 )";
    evaluatePostfix(input);
    return 0;
}

int getPrecedence(char op) {
    // 简单的例子，这里仅用于演示
    if (op == '+' || op == '-') return 1;
    else if (op == '*' || op == '/') return 2;
    else return 0; // 括号
}

void evaluatePostfix(char *postfix) {
    int stack[100], top = -1;
    char temp;

    while (*postfix != '\0') {
        if (*postfix >= '0' && *postfix <= '9') { // 数字
            int num = 0;
            while (*postfix >= '0' && *postfix <= '9') {
                num = num * 10 + (*postfix - '0');
                postfix++;
            }
            postfix--;
            stack[++top] = num;
        } else if (*postfix == '(') { // 左括号
            postfix++;
        } else if (*postfix == ')') { // 右括号
            for (int i = top; i >= 0; i--) {
                if (stack[i] == '(') {
                    top = i - 1;
                    break;
                }
            }
            postfix++;
        } else { // 运算符
            int val2 = stack[top--];
            int val1 = stack[top--];

            switch (*postfix) {
                case '+':
                    stack[top++] = val1 + val2;
                    break;
                case '-':
                    stack[top++] = val1 - val2;
                    break;
                case '*':
                    stack[top++] = val1 * val2;
                    break;
                case '/':
                    if (val2 != 0)
                        stack[top++] = val1 / val2;
                    else
                        printf("Error: Division by zero.\n");
                    break;
                default:
                    printf("Invalid operator '%c'.\n", *postfix);
                    break;
            }
        }
    }

    if (top > 0)
        printf("Output: %d\n", stack[top]);
    else
        printf("Error: Invalid expression.\n");
}