C语言基于栈的中缀表达式求值
时间: 2023-07-26 14:23:48 浏览: 50
中缀表达式求值需要用到栈来辅助计算,具体步骤如下:
1. 初始化一个操作数栈和一个运算符栈。
2. 从左到右扫描中缀表达式,遇到操作数直接入操作数栈。
3. 遇到运算符时,比较其与运算符栈栈顶运算符的优先级:
1. 如果该运算符优先级高于运算符栈栈顶运算符优先级,直接入运算符栈。
2. 否则,将运算符栈栈顶运算符弹出并将其与操作数栈栈顶的两个操作数进行运算,得到的结果再入操作数栈,直到该运算符可以入栈。
4. 如果遇到左括号“(”,直接入运算符栈。
5. 如果遇到右括号“)”,将运算符栈栈顶的运算符弹出并将其与操作数栈栈顶的两个操作数进行运算,得到的结果再入操作数栈,直到遇到左括号“(”,将其弹出。
6. 当扫描完中缀表达式后,若运算符栈中还有运算符,则依次弹出运算符并进行运算,直到运算符栈为空。
7. 最终操作数栈中的栈顶元素即为中缀表达式的计算结果。
下面是一个C语言函数,实现对中缀表达式求值的功能:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct {
char op; // 运算符
int priority; // 优先级
} Operator;
void push_op(Operator *stack, int *top, char op, int priority) {
Operator tmp = {op, priority};
stack[++(*top)] = tmp;
}
char pop_op(Operator *stack, int *top) {
return stack[(*top)--].op;
}
int get_priority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
default:
return -1; // 非法运算符
}
}
int eval(char *expression) {
int operand_stack[100];
int operand_top = -1;
Operator operator_stack[100];
int operator_top = -1;
int num = 0; // 用于拼接多位数
int i = 0;
char c = expression[i];
while (c != '\0') {
if (isdigit(c)) {
num = num * 10 + (c - '0');
} else {
if (num != 0) {
operand_stack[++operand_top] = num;
num = 0;
}
if (c == '+' || c == '-' || c == '*' || c == '/') {
int p = get_priority(c);
while (operator_top >= 0 && operator_stack[operator_top].priority >= p) {
char op = pop_op(operator_stack, &operator_top);
int b = operand_stack[operand_top--];
int a = operand_stack[operand_top--];
switch (op) {
case '+':
operand_stack[++operand_top] = a + b;
break;
case '-':
operand_stack[++operand_top] = a - b;
break;
case '*':
operand_stack[++operand_top] = a * b;
break;
case '/':
operand_stack[++operand_top] = a / b;
break;
}
}
push_op(operator_stack, &operator_top, c, p);
} else if (c == '(') {
push_op(operator_stack, &operator_top, c, 0);
} else if (c == ')') {
while (operator_stack[operator_top].op != '(') {
char op = pop_op(operator_stack, &operator_top);
int b = operand_stack[operand_top--];
int a = operand_stack[operand_top--];
switch (op) {
case '+':
operand_stack[++operand_top] = a + b;
break;
case '-':
operand_stack[++operand_top] = a - b;
break;
case '*':
operand_stack[++operand_top] = a * b;
break;
case '/':
operand_stack[++operand_top] = a / b;
break;
}
}
operator_top--;
} else {
printf("Invalid operator: %c\n", c);
exit(1);
}
}
i++;
c = expression[i];
}
if (num != 0) {
operand_stack[++operand_top] = num;
}
while (operator_top >= 0) {
char op = pop_op(operator_stack, &operator_top);
int b = operand_stack[operand_top--];
int a = operand_stack[operand_top--];
switch (op) {
case '+':
operand_stack[++operand_top] = a + b;
break;
case '-':
operand_stack[++operand_top] = a - b;
break;
case '*':
operand_stack[++operand_top] = a * b;
break;
case '/':
operand_stack[++operand_top] = a / b;
break;
}
}
return operand_stack[0];
}
int main() {
char expression[100];
printf("Please input an infix expression: ");
scanf("%s", expression);
int result = eval(expression);
printf("Result: %d\n", result);
return 0;
}
```
这个函数接受一个中缀表达式字符串作为输入,返回计算结果。注意,这个函数没有对输入表达式的合法性进行检查,如果表达式不合法,可能会导致程序崩溃。