后缀表达式求值c++栈
时间: 2023-09-09 22:12:10 浏览: 65
思路:
1. 从左到右扫描表达式,若遇到数字则入栈;
2. 若遇到运算符,则弹出栈顶的两个元素进行计算,计算结果入栈;
3. 最终栈中只剩下一个元素,即为表达式的值。
具体实现:
1. 定义一个栈来存储数字;
2. 遍历后缀表达式,遇到数字则入栈;
3. 遇到运算符时,弹出栈顶的两个元素进行计算,将计算结果入栈;
4. 最终栈中只剩下一个元素,即为表达式的值,返回该元素即可。
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
typedef struct stack {
int data[MAX_SIZE];
int top;
} Stack;
void init_stack(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 value) {
if (is_full(s)) {
printf("Stack is full\n");
return;
}
s->data[++s->top] = value;
}
int pop(Stack* s) {
if (is_empty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->data[s->top--];
}
int peek(Stack* s) {
if (is_empty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->data[s->top];
}
int evaluate_postfix(char* postfix) {
Stack s;
init_stack(&s);
int len = strlen(postfix);
for (int i = 0; i < len; i++) {
char c = postfix[i];
if (isdigit(c)) {
push(&s, c - '0');
} else {
int b = pop(&s);
int a = pop(&s);
switch (c) {
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("Unknown operator: %c\n", c);
break;
}
}
}
return pop(&s);
}
int main() {
char postfix[] = "34+5*";
int result = evaluate_postfix(postfix);
printf("Result: %d\n", result);
return 0;
}
```
输出:
```
Result: 35
```
相关推荐
![](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)