用C/C++实现中缀表达式求值的算法
时间: 2024-05-11 21:14:09 浏览: 31
下面是一种用C语言实现中缀表达式求值的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
typedef struct Stack {
int top;
int data[MAX_SIZE];
} Stack;
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");
exit(1);
}
s->top++;
s->data[s->top] = value;
}
int pop(Stack *s) {
if (is_empty(s)) {
printf("Stack is empty.\n");
exit(1);
}
int value = s->data[s->top];
s->top--;
return value;
}
int peek(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;
}
}
int evaluate(int op1, int op2, char op) {
switch (op) {
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
default:
return 0;
}
}
int infix_to_postfix(char *infix, char *postfix) {
int i, j;
Stack s;
s.top = -1;
for (i = 0, j = 0; infix[i] != '\0'; i++) {
if (isdigit(infix[i])) {
postfix[j++] = 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)) {
printf("Invalid expression.\n");
exit(1);
}
pop(&s);
} else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
while (!is_empty(&s) && peek(&s) != '(' && priority(infix[i]) <= priority(peek(&s))) {
postfix[j++] = pop(&s);
}
push(&s, infix[i]);
} else {
printf("Invalid character: %c\n", infix[i]);
exit(1);
}
}
while (!is_empty(&s)) {
if (peek(&s) == '(') {
printf("Invalid expression.\n");
exit(1);
}
postfix[j++] = pop(&s);
}
postfix[j] = '\0';
return j;
}
int evaluate_postfix(char *postfix) {
int i;
Stack s;
s.top = -1;
for (i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
push(&s, postfix[i] - '0');
} else if (postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/') {
int op2 = pop(&s);
int op1 = pop(&s);
int result = evaluate(op1, op2, postfix[i]);
push(&s, result);
} else {
printf("Invalid character: %c\n", postfix[i]);
exit(1);
}
}
if (s.top != 0) {
printf("Invalid expression.\n");
exit(1);
}
return pop(&s);
}
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix[strcspn(infix, "\n")] = '\0';
int length = infix_to_postfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
int result = evaluate_postfix(postfix);
printf("Result: %d\n", result);
return 0;
}
```
该算法使用两个栈,一个用于转换中缀表达式为后缀表达式,另一个用于求解后缀表达式。其中,转换中缀表达式为后缀表达式的过程中,遇到操作数直接输出到后缀表达式中,遇到左括号直接压入栈中,遇到右括号则将栈中元素弹出直到遇到左括号,并将左右括号都丢弃。遇到操作符时,如果栈顶元素为左括号,则直接将操作符压入栈中;否则,将栈中优先级大于等于当前操作符的元素都弹出,直到栈为空或栈顶元素为左括号,并将当前操作符压入栈中。转换完成后,如果栈中还有元素,则依次弹出并输出到后缀表达式中。
求解后缀表达式的过程中,遇到操作数则直接压入栈中,遇到操作符则弹出栈顶的两个元素作为操作数,计算结果并将结果压入栈中。最终,如果栈中只有一个元素,则该元素即为表达式的值。如果栈中元素多于一个,则表明表达式有误。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)