用栈和队列编写表达式求值，c语言实现

在C语言中，我们可以利用栈（Stack）和队列（Queue）的数据结构来解析并计算简单的算术表达式。这种算法通常被称为逆波兰表示法（Reverse Polish Notation，RPN）也叫做后缀表达式。这种方法避免了括号的嵌套问题，降低了处理复杂度。

下面是一个简单的步骤描述：

1. **转换表达式**：首先，将输入的前缀或 infix 表达式转换成后缀表达式。这一步可以使用栈，遍历输入表达式的字符，遇到操作数就入栈，遇到运算符则出栈直到找到左括号或等于该运算符优先级的操作符，然后将当前操作符压入栈。

2. **计算后缀表达式**：遍历转换后的后缀表达式的栈，对于每个元素，如果它是操作数，则直接相加；如果是运算符，从栈顶取出两个操作数，进行相应运算，并把结果放回栈中。

3. **最终结果**：栈中剩下的一个元素就是表达式的结果。

以下是部分关键代码示例：

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

#define MAX 50

// 运算符优先级
int priority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

void push(int arr[], int val, int n) {
    // ...（这里实现数组的入栈操作）
}

double pop(int arr[], int n) {
    // ...（这里实现数组的出栈操作）
}

double calculate(char* exp) {
    int len = strlen(exp);
    char stack[MAX];
    int top = -1;
    for (int i = 0; i < len; ++i) {
        if (isdigit(exp[i])) {
            push(stack, exp[i] - '0', MAX);
        } else {
            while (top >= 0 && priority(exp[i]) <= priority(stack[top])) {
                double b = pop(stack, MAX);
                double a = pop(stack, MAX);
                switch (exp[i]) {
                    case '+':
                        push(stack, a + b, MAX);
                        break;
                    case '-':
                        push(stack, a - b, MAX);
                        break;
                    case '*':
                        push(stack, a * b, MAX);
                        break;
                    case '/':
                        push(stack, a / b, MAX);
                        break;
                }
            }
            push(stack, exp[i], MAX);
        }
    }
    return pop(stack, MAX);
}

int main() {
    char exp[] = "2 * 3 + 4";
    double result = calculate(exp);
    printf("Result: %.2f\n", result);
    return 0;
}