基于栈的中缀算术表达式求值
时间: 2023-11-10 18:01:14 浏览: 84
基于栈的中缀算术表达式求值是一种计算中缀表达式的方法。这种方法通过维护两个栈,一个操作数栈和一个运算符栈,来按照运算符的优先级进行计算。具体步骤如下:
1. 创建一个空的操作数栈和一个空的运算符栈。
2. 从左到右遍历中缀表达式的每个字符。
3. 如果当前字符是数字,则将其解析为一个操作数并将其压入操作数栈。
4. 如果当前字符是运算符,并且运算符栈为空,或者当前运算符的优先级高于或等于运算符栈顶运算符的优先级,则将当前运算符压入运算符栈。
5. 如果当前字符是运算符,并且当前运算符的优先级低于运算符栈顶运算符的优先级,则从运算符栈弹出栈顶运算符,从操作数栈弹出两个操作数进行计算,然后将计算结果压入操作数栈。重复此过程直到当前运算符的优先级大于或等于运算符栈顶运算符的优先级,然后将当前运算符压入运算符栈。
6. 如果当前字符是左括号,则将其压入运算符栈。
7. 如果当前字符是右括号,则从运算符栈中弹出运算符,从操作数栈中弹出两个操作数进行计算,然后将计算结果压入操作数栈。重复此过程直到遇到左括号为止。
8. 遍历完整个中缀表达式后,从运算符栈中依次弹出运算符,从操作数栈中依次弹出两个操作数进行计算,然后将计算结果压入操作数栈。
9. 最后,操作数栈中的唯一元素即为中缀表达式的计算结果。
相关问题
第1关 基于栈的中缀算术表达式求值
题目描述
给定一个中缀算术表达式,计算它的值。
例如,给定表达式 3+4*5-2,其值为 3+4*5-2=21。
输入格式
共一行,为中缀算术表达式,其中不包含空格。
输出格式
共一行,为表达式的值。
数据范围
输入样例
3+4*5-2
输出样例
21
算法1
(栈) $O(n)$
栈中存储数字和运算符,遇到数字直接入栈,遇到运算符时,判断当前运算符和栈顶运算符的优先级,如果当前运算符优先级高于栈顶运算符,则直接入栈,如果当前运算符优先级低于等于栈顶运算符,则弹出栈顶的运算符和两个数字进行运算,并将结果压入栈中。最后栈中只剩下一个数字,就是表达式的值。
时间复杂度
栈的大小为表达式的长度,所以时间复杂度为 O(n)
Python3 代码
C++ 代码
算法2
(递归) $O(n)$
最简单的方法是使用递归,将表达式分为两个部分,左边和右边,然后递归计算左边和右边的值,然后根据运算符计算结果。
时间复杂度
递归深度为表达式中运算符的个数,时间复杂度为 O(n)
Python3 代码
C++ 代码
算法3
(栈) $O(n)$
时间复杂度
参考文献
Python3 代码
C++ 代码
算法4
(递归) $O(n)$
时间复杂度
参考文献
C++ 代码
用C语言写基于栈的中缀算术表达式求值
好的,您可以这样写一个基于栈的中缀表达式求值程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 50
typedef int ElemType;
typedef struct {
ElemType data[MAX_SIZE];
int top;
} Stack;
void push(Stack *s, ElemType e) {
if (s->top == MAX_SIZE) {
printf("stack overflow\n");
exit(1);
}
s->data[s->top++] = e;
}
ElemType pop(Stack *s) {
if (s->top == 0) {
printf("stack underflow\n");
exit(1);
}
return s->data[--s->top];
}
ElemType peek(Stack *s) {
if (s->top == 0) {
printf("stack empty\n");
exit(1);
}
return s->data[s->top - 1];
}
int is_op(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int cmp_op(char op1, char op2) {
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return 1;
return 0;
}
int eval(char op, int b, int a) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return 0;
}
int eval_expr(char *expr) {
Stack op_stack, num_stack;
op_stack.top = 0;
num_stack.top = 0;
int i = 0;
while (expr[i] != '\0') {
if (isdigit(expr[i])) {
int num = 0;
while (isdigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
i++;
}
push(&num_stack, num);
} else if (is_op(expr[i])) {
while (op_stack.top > 0 && !cmp_op(expr[i], peek(&op_stack))) {
int b = pop(&num_stack);
int a = pop(&num_stack);
char op = pop(&op_stack);
int result = eval(op, b, a);
push(&num_stack, result);
}
push(&op_stack, expr[i]);
i++;
} else if (expr[i] == '(') {
push(&op_stack, '(');
i++;
} else if (expr[i] == ')') {
while (peek(&op_stack) != '(') {
int b = pop(&num_stack);
int a = pop(&num_stack);
char op = pop(&op_stack);
int result = eval(op, b, a);
push(&num_stack, result);
}
pop(&op_stack);
i++;
} else {
i++;
}
}
while (op_stack.top > 0) {
int b = pop(&num_stack);
int a = pop(&num_stack);
char op = pop(&op_stack);
int result = eval(op, b, a);
push(&num_stack, result);
}
return pop(&num_stack);
}
int main(void) {
char expr[MAX_SIZE];
printf("Enter an infix expression: ");
scanf("%s", expr);
int result = eval_expr(expr);
printf("Result: %d\n", result);
return 0;
}
```
该程序使用两个栈来实现中缀表达式求值,一个保存操作数,一个保存操作符。遍历表达式的每个字符,如果是数字,则从当前位置开始解析数字,并将其压入操作数栈中;如果是操作符,则依次将栈顶符号与当前符号比较优先级,如果栈顶符号优先级较高,则弹出两个操作数和一个操作符,计算出结果并将其压入操作数栈中,否则将当前符号压入操作符栈中;如果是左括号,则直接将其压入操作符栈中;如果是右括号,则依次弹出操作数栈和操作符栈中的元素,直到遇到左括号为止,并将计算结果压入操作数栈中;其他字符则忽略。最后,当操作符栈不为空时,依次弹出操作数栈和操作符栈中的元素,计算出最终结果。