逆波兰表达式栈实现c
时间: 2024-06-12 08:09:58 浏览: 69
逆波兰表达式是一种将运算符放在操作数后面的表达式,例如中缀表达式 3 + 4 * 5 可以转换为后缀表达式 3 4 5 * +。实现逆波兰表达式的计算可以使用栈来实现,具体步骤如下:
1. 创建一个栈,用于存储操作数和中间结果。
2. 从左到右遍历逆波兰表达式中的每个元素。
3. 如果当前元素是操作数,则将其压入栈中。
4. 如果当前元素是运算符,则从栈中弹出两个操作数,进行运算,并将结果压入栈中。
5. 遍历完整个表达式后,栈中只剩下一个元素,即为表达式的计算结果。
以下是逆波兰表达式栈实现的 C 代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
typedef struct {
int top;
int data[MAX_SIZE];
} Stack;
void init(Stack *s) {
s->top = -1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_full(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int x) {
if (is_full(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = x;
}
int pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
int calculate(char *expr) {
Stack s;
init(&s);
char *token = strtok(expr, " ");
while (token != NULL) {
if (isdigit(token[0])) {
push(&s, atoi(token));
} else {
int b = pop(&s);
int a = pop(&s);
switch (token[0]) {
case '+':
push(&s, a + b);
break;
case '-':
push(&s, a - b);
break;
case '*':
push(&s, a * b);
break;
case '/':
push(&s, a / b);
break;
default:
printf("Invalid operator: %c\n", token[0]);
exit(1);
}
}
token = strtok(NULL, " ");
}
int result = pop(&s);
if (!is_empty(&s)) {
printf("Invalid expression\n");
exit(1);
}
return result;
}
int main() {
char expr[] = "3 4 5 * +";
int result = calculate(expr);
printf("%d\n", result);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)