用c语言实现算术表达式求值

在C语言中，实现算术表达式的求值通常需要采用递归解析和逆波兰表示法(RPN，也称为后缀表达式)。这是因为使用传统的前缀或 infix 表示法(如 "2 + 3 * 4")在处理复杂的运算优先级时会变得复杂。以下是基本步骤： 1. **逆波兰表达式转换**: 将给定的中缀表达式转换成后缀表达式，可以使用两个栈，一个存放操作数，另一个存放操作符。遍历表达式，如果遇到数字就入栈；如果是操作符，则比较其优先级，将高于或等于当前操作符优先级的操作符出栈，直到找到一个优先级更低的或为空，然后将该操作符压入栈，最后将遇到的操作数依次入栈。 2. **计算RPN表达式**: 创建一个变量用于存储结果，并从左到右扫描RPN表达式的栈。每次遇到一个操作数，弹出栈顶的操作数，做相应的数学运算（如加、减、乘、除），并将结果压回栈中。当只剩下一个元素时，栈顶即为最终的结果。 ```c #include <stdio.h> #include <stdlib.h> #include <string.h> // Function to evaluate an RPN expression int evalRPN(char* tokens, int n) { stack_t* s = (stack_t*)malloc(sizeof(stack_t)); int i; for (i = 0; i < n; ++i) { if (isdigit(tokens[i])) { int num = 0; while (isdigit(tokens[i])) { num = num * 10 + (tokens[i] - '0'); ++i; } push(s, num); } else { int op2 = pop(s); int op1 = pop(s); switch (tokens[i]) { case '+': push(s, op1 + op2); break; case '-': push(s, op1 - op2); break; case '*': push(s, op1 * op2); break; case '/': push(s, op1 / op2); break; // Add more cases for other operators if needed } } } return top(s); // Return the final result } // Stack implementation for storing integers typedef struct stack_t { int* data; size_t capacity; size_t top; } stack_t; void push(stack_t* s, int val) { if (s->top == s->capacity) { s->capacity *= 2; s->data = realloc(s->data, sizeof(int) * s->capacity); } s->data[s->top++] = val; } int pop(stack_t* s) { if (s->top == 0) return INT_MIN; return s->data[--s->top]; } int top(stack_t* s) { return (s->top == 0) ? INT_MIN : s->data[s->top - 1]; } int main() { char* expr = "2 3 + 4 *"; int n = strlen(expr); printf("Result: %d\n", evalRPN(expr, n)); // Output: 14 free(s->data); free(s); return 0; } ```