用C语言利用顺序栈完成将中缀表达式转化为后缀表达式,并计算出其值
时间: 2024-05-07 21:20:53 浏览: 15
中缀表达式转后缀表达式可以使用栈完成,具体步骤如下:
1. 初始化两个栈:运算符栈和后缀表达式栈。
2. 从左到右扫描中缀表达式。
3. 如果是数字,直接压入后缀表达式栈。
4. 如果是左括号,直接压入运算符栈。
5. 如果是右括号,则将运算符栈中的运算符弹出并压入后缀表达式栈,直到遇到左括号,将左括号弹出但不压入后缀表达式栈。
6. 如果是运算符,比较其与运算符栈顶元素的优先级:
1. 如果运算符栈为空,或栈顶运算符为左括号,则直接压入运算符栈。
2. 否则,若优先级比栈顶运算符的优先级高或相等,则直接压入运算符栈。
3. 否则,将运算符栈顶的运算符弹出并压入后缀表达式栈,再次转到步骤 6。
7. 重复步骤 3-6,直到表达式的最右边。
8. 将运算符栈中的所有运算符依次弹出并压入后缀表达式栈。
9. 最后,后缀表达式栈中的元素顺序即为后缀表达式的逆序。
10. 遍历后缀表达式栈,依次弹出元素,如果是数字则压入数栈,如果是运算符则弹出数栈中的两个数进行运算并将结果压入数栈。
11. 最后数栈中的元素即为表达式的值。
下面是一个完整的C语言程序实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
typedef struct {
char data[MAX_SIZE];
int top;
} 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, char c) {
if (is_full(s)) {
printf("stack is full\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (is_empty(s)) {
printf("stack is empty\n");
exit(1);
}
return s->data[s->top--];
}
char top(Stack *s) {
if (is_empty(s)) {
printf("stack is empty\n");
exit(1);
}
return s->data[s->top];
}
int priority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
void infix_to_postfix(char *infix, char *postfix) {
Stack op_stack;
init(&op_stack);
int i = 0, j = 0;
while (infix[i]) {
if (isdigit(infix[i])) {
postfix[j++] = infix[i++];
while (isdigit(infix[i])) {
postfix[j++] = infix[i++];
}
postfix[j++] = ' ';
} else if (infix[i] == '(') {
push(&op_stack, infix[i]);
i++;
} else if (infix[i] == ')') {
while (top(&op_stack) != '(') {
postfix[j++] = pop(&op_stack);
postfix[j++] = ' ';
}
pop(&op_stack);
i++;
} else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
while (!is_empty(&op_stack) && top(&op_stack) != '(' && priority(infix[i]) <= priority(top(&op_stack))) {
postfix[j++] = pop(&op_stack);
postfix[j++] = ' ';
}
push(&op_stack, infix[i]);
i++;
} else {
printf("invalid character: %c\n", infix[i]);
exit(1);
}
}
while (!is_empty(&op_stack)) {
postfix[j++] = pop(&op_stack);
postfix[j++] = ' ';
}
postfix[j] = '\0';
}
int evaluate_postfix(char *postfix) {
Stack num_stack;
init(&num_stack);
int i = 0;
while (postfix[i]) {
if (isdigit(postfix[i])) {
int num = 0;
while (isdigit(postfix[i])) {
num = num * 10 + (postfix[i] - '0');
i++;
}
push(&num_stack, num);
} else if (postfix[i] == '+') {
int b = pop(&num_stack);
int a = pop(&num_stack);
push(&num_stack, a + b);
i++;
} else if (postfix[i] == '-') {
int b = pop(&num_stack);
int a = pop(&num_stack);
push(&num_stack, a - b);
i++;
} else if (postfix[i] == '*') {
int b = pop(&num_stack);
int a = pop(&num_stack);
push(&num_stack, a * b);
i++;
} else if (postfix[i] == '/') {
int b = pop(&num_stack);
int a = pop(&num_stack);
push(&num_stack, a / b);
i++;
} else if (postfix[i] == ' ') {
i++;
} else {
printf("invalid character: %c\n", postfix[i]);
exit(1);
}
}
return pop(&num_stack);
}
int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
printf("Input infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix_to_postfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
printf("Result: %d\n", evaluate_postfix(postfix));
return 0;
}
```
注意事项:
1. 程序中使用了一个辅助函数 `isdigit` 判断字符是否为数字,需要包含头文件 `ctype.h`。
2. 程序中使用了一个辅助函数 `fgets` 从标准输入中读取一行字符串,需要包含头文件 `stdio.h`。
3. 在输出后缀表达式时,每个数字后面需要加上一个空格,以便于后面的计算。
4. 在计算后缀表达式时,需要注意除数不能为零的情况,此时应该输出错误信息并退出程序。