中缀表达式转后缀表达式并求值,c+
时间: 2024-06-12 14:05:43 浏览: 22
设计思路:
1. 定义一个栈,用于存储运算符。
2. 从左到右扫描中缀表达式的每个元素,如果是数字,直接输出;如果是运算符,比较它与栈顶运算符的优先级,如果当前运算符优先级较高,直接入栈;否则,将栈顶运算符出栈输出,直到当前运算符可以入栈。
3. 如果扫描完了中缀表达式,但是栈中还有运算符,将它们全部出栈输出。
4. 得到后缀表达式后,再定义一个栈,用于存储操作数,从左到右扫描后缀表达式,如果是数字,直接入栈;如果是运算符,将栈顶两个元素出栈进行运算,将运算结果入栈。
5. 最终得到栈中的唯一元素即为后缀表达式的值。
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
typedef struct {
char 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, char c) {
if (is_full(s)) {
printf("stack overflow\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (is_empty(s)) {
printf("stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
char peek(Stack *s) {
if (is_empty(s)) {
printf("stack underflow\n");
exit(1);
}
return s->data[s->top];
}
int is_operator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int priority(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
void infix_to_postfix(char *infix, char *postfix) {
Stack s;
init_stack(&s);
int i, j;
for (i = 0, j = 0; infix[i] != '\0'; i++) {
if (isdigit(infix[i])) {
postfix[j++] = infix[i];
} else if (is_operator(infix[i])) {
while (!is_empty(&s) && is_operator(peek(&s)) && priority(peek(&s)) >= priority(infix[i])) {
postfix[j++] = pop(&s);
}
push(&s, infix[i]);
} else if (infix[i] == '(') {
push(&s, infix[i]);
} else if (infix[i] == ')') {
while (!is_empty(&s) && peek(&s) != '(') {
postfix[j++] = pop(&s);
}
if (!is_empty(&s) && peek(&s) == '(') {
pop(&s);
}
}
}
while (!is_empty(&s)) {
postfix[j++] = pop(&s);
}
postfix[j] = '\0';
}
int evaluate_postfix(char *postfix) {
Stack s;
init_stack(&s);
int i, a, b, c;
for (i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
push(&s, postfix[i] - '0');
} else if (is_operator(postfix[i])) {
b = pop(&s);
a = pop(&s);
switch (postfix[i]) {
case '+':
c = a + b;
break;
case '-':
c = a - b;
break;
case '*':
c = a * b;
break;
case '/':
c = a / b;
break;
}
push(&s, c);
}
}
return pop(&s);
}
int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix[strlen(infix) - 1] = '\0';
infix_to_postfix(infix, postfix);
printf("The postfix expression is: %s\n", postfix);
int result = evaluate_postfix(postfix);
printf("The value of the expression is: %d\n", result);
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)