如何用C语言实现栈来转换并求值前缀、中缀和后缀表达式?
时间: 2024-12-14 19:18:59 浏览: 90
在C语言中,我们可以使用栈数据结构来处理前缀(Prefix)、中缀(Infix)和后缀(Postfix)表达式的转换和求值。这里是一个简单的流程:
1. **中缀转后缀(Reverse Polish Notation, RPN)**:
- 遇到运算符时,将其推入栈中,直到遇到左括号或遇到更高优先级的运算符。
- 遇到数字时,直接添加到结果字符串(后缀表示法)。
- 遇到右括号时,将栈顶的元素依次弹出并添加到结果,直到遇到左括号。
2. **后缀求值**:
- 从后缀表达式开始遍历,遇到数字就把它压入栈里。
- 遇到运算符时,从栈中取出两个操作数进行计算,并把结果压回栈中。
- 最终栈顶剩下的就是表达式的计算结果。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TOKENS 50
#define PRECEDENCE(OP) 2
// 函数用于比较运算符优先级
int comparePrec(char op1, char op2);
// 后缀求值函数
double evaluate(char *postfix);
// 主函数示例
int main() {
char infix[] = "4*(5+3)";
char postfix[MAX_TOKENS];
strcpy(postfix, infix);
int i, j;
// 中缀转后缀
for (i = 0; infix[i]; ) {
if (isdigit(infix[i])) {
while (isdigit(infix[i])) {
postfix[j++] = infix[i++];
}
postfix[j] = '\0';
} else if (infix[i] == '(' || infix[i] == ')') {
postfix[j++] = infix[i++];
} else {
while (j > 0 && comparePrec(infix[i], postfix[j - 1]) >= 0) {
postfix[--j] = ' ';
}
postfix[j++] = infix[i++];
while (j > 0 && postfix[j - 1] == '(') {
postfix[--j] = ' ';
}
}
}
postfix[j] = '\0'; // 添加结束符
printf("后缀表达式: %s\n", postfix);
double result = evaluate(postfix);
printf("结果: %.2f\n", result);
return 0;
}
// 运算符优先级比较函数
int comparePrec(char op1, char op2) {
if (PRECEDENCE(op1) == PRECEDENCE(op2)) {
return 0;
}
return PRECEDENCE(op1) < PRECEDENCE(op2) ? -1 : 1;
}
// 后缀表达式求值
double evaluate(char *postfix) {
double stack[MAX_TOKENS] = {0};
int top = -1;
char token;
while ((token = postfix[++top]) != '\0') {
if (isdigit(token)) {
double num = 0.0;
while (isdigit(postfix[top])) {
num = num * 10 + (postfix[top] - '0');
++top;
}
stack[++top] = num;
} else {
double operand2 = stack[top--];
double operand1 = stack[top--];
switch (token) {
case '+':
stack[top++] = operand1 + operand2;
break;
case '-':
stack[top++] = operand1 - operand2;
break;
case '*':
stack[top++] = operand1 * operand2;
break;
case '/':
if (operand2 != 0)
stack[top++] = operand1 / operand2;
else
printf("Error: Division by zero.\n");
break;
default:
printf("Invalid operator.\n");
return 0;
}
}
}
return stack[1];
}
```
阅读全文
相关推荐















