用类C写一个算法对逆波兰式求值
时间: 2024-06-12 10:10:54 浏览: 4
好的,以下是用类C实现对逆波兰式求值的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_STACK_SIZE 100
typedef struct {
int top;
double data[MAX_STACK_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_STACK_SIZE - 1;
}
void push(Stack *s, double x) {
if (is_full(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = x;
}
double pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
double eval(char *expr) {
Stack s;
double op1, op2, result;
char *token;
init(&s);
token = strtok(expr, " ");
while (token != NULL) {
if (isdigit(token[0])) {
push(&s, atof(token));
} else {
op2 = pop(&s);
op1 = pop(&s);
switch (token[0]) {
case '+':
result = op1 + op2;
break;
case '-':
result = op1 - op2;
break;
case '*':
result = op1 * op2;
break;
case '/':
result = op1 / op2;
break;
default:
printf("Invalid operator: %c\n", token[0]);
exit(1);
}
push(&s, result);
}
token = strtok(NULL, " ");
}
return pop(&s);
}
int main() {
char expr[100];
printf("Enter an expression in postfix notation: ");
fgets(expr, 100, stdin);
printf("Result: %f\n", eval(expr));
return 0;
}
```
该算法使用栈来实现对逆波兰式的求值。具体实现过程如下:
1. 初始化一个栈。
2. 从左到右遍历逆波兰式中的每个元素。
3. 如果当前元素是数字,则将其压入栈中。
4. 如果当前元素是运算符,则从栈中弹出两个操作数,进行相应的运算,并将结果压入栈中。
5. 重复步骤2-4,直到遍历完整个逆波兰式。
6. 最后,从栈中弹出的元素即为逆波兰式的求值结果。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)