中缀表达式的计算C语言实现
时间: 2024-11-10 08:24:54 浏览: 30
数据结构——中缀表达式计算【C语言实现】
4星 · 用户满意度95%
在C语言中,中缀表达式(也称为前缀或后缀表达式)的计算通常通过逆波兰表示法(Reverse Polish Notation,RPN)来实现,因为这种形式更适合于栈的操作。以下是简单的步骤:
1. **解析输入表达式**:首先将给定的中缀表达式转换成后缀表达式。这需要使用算法,比如Shunting Yard算法或Knuth-Morris-Pratt算法。
2. **初始化栈和数组**:创建一个空栈用于存放操作数,以及一个数组用于临时存储后缀表达式。
3. **遍历后缀表达式**:从左到右扫描后缀表达式。遇到数字就直接压入栈;遇到运算符则弹出栈顶的两个元素直到遇到优先级较低的运算符或者遇到左括号,然后将当前运算符压入栈。
4. **处理括号**:遇到左括号就直接压入栈;遇到右括号时,直到栈顶的左括号为止,依次弹出并压回栈中的元素,然后再将右括号压入栈。
5. **计算结果**:当遍历完所有后缀表达式,栈中剩下的就是运算顺序对应的数字,从栈顶开始做乘除加减运算即可得到最终的结果。
6. **函数封装**:可以编写一个递归或迭代的函数来处理整个过程,并返回计算结果。
下面是简化的代码示例(仅适用于加减乘除,未包含括号处理):
```c
#include <stdio.h>
#include <stdlib.h>
// Stack operations
int pop(int stack[], int top);
void push(int value, int stack[], int &top);
// Function to evaluate an RPN expression
double evalRPN(char *tokens, int size) {
double stack[size]; // Assuming a fixed-size stack
int top = -1;
char *token;
for (token = tokens; token < tokens + size; ++token) {
if (*token == ' ') continue;
if (*token >= '0' && *token <= '9') { // Number
push(atof(token), stack, top);
} else { // Operator
double num2 = pop(stack, top); // Pop the second operand
double num1 = pop(stack, top); // Pop the first operand
switch (*token) {
case '+':
push(num1 + num2, stack, top);
break;
case '-':
push(num1 - num2, stack, top);
break;
case '*':
push(num1 * num2, stack, top);
break;
case '/':
push(num1 / num2, stack, top);
break;
default:
printf("Invalid operator\n");
}
}
}
return pop(stack, top);
}
int main() {
char* rpn = "2 3 + 4 *"; // Sample input: (2 + 3) * 4
int size = strlen(rpn);
double result = evalRPN(rpn, size);
printf("Result: %.2lf\n", result);
return 0;
}
```
阅读全文