想使用c语言编写将中缀表达式并求值的程序,可一直无法求值,且一直显示栈空
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include
#include
#define Maxop 100
#define infinity 1e9
#define ture 1
#define false 0
#define error -1
typedef char elementtype;
typedef enum { num, opr, end } type;
typedef int position;
typedef struct snode* ptrtosnode;
struct snode
{
elementtype* data;
position top;
int max;
};
typedef ptrtosnode stack;
stack create(int maxsize) {
stack s = (stack)malloc(sizeof(struct snode));
if (s != NULL) {
s->data = (elementtype*)malloc(maxsize * sizeof(elementtype));
s->top = -1;
s->max = maxsize;
return s;
}
}
bool isfull(stack s) {
return(s->top == s->max - 1);
}
bool push(stack s, elementtype x) {
if (isfull(s)) {
printf("stack is full");
return false;
}
else {
s->data[++(s->top)] = x;
return ture;
}
}
bool isempty(stack s) {
return(s->top == -1);
}
elementtype pop(stack s) {
if (isempty(s)) {
printf("stack is empty");
return error;
}
else {
return(s->data[(s->top)--]);
}
}
int judge(char x, char y) {
int a = 0, b = 0;
switch (x)
{
case'+':a = 1; break;
case'-':a = 1; break;
case'':a = 2; break;
case'/':a = 2; break;
default:
break;
}
switch (y)
{
case'+':b = 1; break;
case'-':b = 1; break;
case'':b = 2; break;
case'/':b = 2; break;
default:
break;
}
if (a > b) { return ture; }
else
{
return false;
}
}
char* transform(char infix[]) {
stack temp = create(Maxop);
int i = 0,n=0;
char suffix[Maxop];
while (infix[i] != '\0') {
if (infix[i] == ' ') { suffix[n] = infix[i]; n++; i++; }
else if (infix[i] >= '0' && infix[i] < '10') {
suffix[n] = infix[i];
i++; n++;
}
else if (infix[i] == '(') {
push(temp, infix[i]);
i++;
}
else if (infix[i] == ')') {
while (temp->data != '(') {
suffix[n] = pop(temp);
n++;
}
pop(temp);
i++;
}
else {
while (!judge(infix[i], temp->data)) {
suffix[n] = pop(temp);
n++; i++;
}
push(temp, infix[i]);
i++;
}
}
while (infix[i] == '\0' && !isempty(temp)) { suffix[n] = pop(temp); n++; }
suffix[n] = '\0';
return suffix;
}
type getop(char* expr, int* start, char* str) {
int i = 0;
while ((str[0] = expr[(*start)++]) == ' ');
while (str[i] != ' ' && str[i] != '\0')
str[++i] = expr[(*start)++];
if (str[i] == '\0')
(*start)--;
str[i] = '\0';
if (i == 0)return end;
else if (isdigit(str[0]) || isdigit(str[1]))
return num;
else
return opr;
}
double postfixexp(char* expr) {
typedef double elementtype;
stack s;
type t;
double op1, op2;
char str[Maxop];
int start = 0;
s = create(Maxop);
op1 = op2 = 0;
while ((t = getop(expr, &start, str)) != end) {
if (t == num)
push(s, atof(str));
else {
if (!isempty(s))op2 = pop(s);
else op2 = infinity;
if (!isempty(s))op1 = pop(s);
else op2 = infinity;
switch (str[0])
{
case'+':push(s, op1 + op2); break;
case'*':push(s, op1 * op2); break;
case'-':push(s, op1 - op2); break;
case'/':
if (op2 != 0.0)
push(s, op1 / op2);
else {
printf("错误:除法分母为0");
op2 = infinity;
}
break;
default:printf("错误:未知运算符%s\n", str);
op2 = infinity;
break;
}
if (op2 >= infinity)break;
}
}
if (op2 < infinity)
if (!isempty(s))
op2 = pop(s);
else op2 = infinity;
free(s);
return op2;
}
int main() {
char expr[Maxop];
double f;
gets(expr);
transform(expr);
for (int i = 0; expr[i] != '\0'; i++) { printf("%c", expr[i]); }
f = postfixexp(expr);
if (f < infinity)
printf("%.4f\n", f);
else
printf("表达式错误\n");
return 0;
}
通过transform函数将中缀表达式转化为后缀表达式
>