写一段代码,用c++的栈和逆波兰算法实现表达式求解,要求代码能实现从中缀表达式转换成后缀表达式后也能求出表达式的值。
时间: 2023-06-08 18:04:44 浏览: 103
好的,我可以为您提供一个基于C语言的栈和逆波兰算法实现表达式求解的代码,代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
float stack[MAX_SIZE];
int top = -1;
void push(float val) {
if (top == MAX_SIZE - 1) {
printf("Stack overflow\n");
exit(EXIT_FAILURE);
}
stack[++top] = val;
}
float pop() {
if (top == -1) {
printf("Stack underflow\n");
exit(EXIT_FAILURE);
}
return stack[top--];
}
int is_operator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
int priority(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
}
return 0;
}
float evaluate(char *expr) {
char ch;
float val1, val2, res;
int i = 0;
while ((ch = expr[i++]) != '\0') {
if (isdigit(ch)) {
push(ch - '0');
} else if (is_operator(ch)) {
val2 = pop();
val1 = pop();
switch(ch) {
case '+': push(val1 + val2); break;
case '-': push(val1 - val2); break;
case '*': push(val1 * val2); break;
case '/': push(val1 / val2); break;
}
} else {
printf("Invalid expression\n");
exit(EXIT_FAILURE);
}
}
res = pop();
return res;
}
void infix_to_postfix(char *infix, char *postfix) {
char ch, op;
int i = 0, j = 0;
while ((ch = infix[i++]) != '\0') {
if (isdigit(ch)) {
postfix[j++] = ch;
} else if (ch == '(') {
push(ch);
} else if (ch == ')') {
while ((op = pop()) != '(') {
postfix[j++] = op;
}
} else if (is_operator(ch)) {
while (top != -1 && stack[top] != '(' && priority(stack[top]) >= priority(ch)) {
postfix[j++] = pop();
}
push(ch);
} else {
printf("Invalid expression\n");
exit(EXIT_FAILURE);
}
}
while (top != -1 && stack[top] != '(') {
postfix[j++] = pop();
}
postfix[j] = '\0';
}
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
float res;
printf("Enter an infix expression: ");
scanf("%s", infix);
infix_to_postfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
res = evaluate(postfix);
printf("Result: %f\n", res);
return 0;
}
```
在这段代码中,我们使用栈来实现了中缀表达式转换成后缀表达式的操作,并且使用逆波兰算法来实现了表达式求解,并且当遇到非法字符时,程序会输出提示信息并退出。
注意:本代码存在一些缺陷,例如没有进行边界检查等,如果需要在实际开发中使用,请自行完善。
阅读全文