超级英雄追妻手册微盘:把中缀表达式转化为后缀表达式的源程序

中缀表达式转化成后缀表达式并求值的算法

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXNUM 100
typedef int DataType;
struct SeqStack
{ DataType s[MAXNUM];
int t;
};
typedef struct SeqStack *PSeqStack;
PSeqStack createEmptyStack_seq()
{
PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack == NULL)
printf("Out of space!!\n");
else
pastack->t = -1;
return pastack;
} int isEmptyStack_seq(PSeqStack pastack)
{
return pastack->t == -1;
} void push_seq(PSeqStack pastack, DataType x)
{
if (pastack->t >= MAXNUM - 1)
printf("Overflow!\n");
else
{
pastack->t = pastack->t + 1;
pastack->s[pastack->t] = x;
}
} void pop_seq(PSeqStack pastack)
{
if (pastack->t == -1)
printf("Underflow!\n");
else
pastack->t = pastack->t - 1;
} DataType top_seq(PSeqStack pastack)
{
return pastack->s[pastack->t];
} int infixtoSuffix(const char * infix, char * suffix)
{ /*将中缀表达式转换为后缀表达式，顺利转换返回true，若转换过程中发现中缀表达式非法则返回false*/
int state_int = FALSE;
/*state_int记录状态，等于true表示刚读入的是数字字符，等于false表示刚读入的不是数字字符，
设置这个变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/
char c, c2;
PSeqStack ps = createEmptyStack_seq(); /*运算符栈*/
int i, j = 0;
if (infix[0] == '\0')
return FALSE; /*不允许出现空表达式*/
for (i = 0; infix[i] != '\0'; i++)
{
c = infix[i];
switch (c)
{
case ' ':
case '\t':
case '\n':
if (state_int == TRUE)
suffix[j++] = ' ';/*状态从true转换为false时输出一个空格*/
state_int = FALSE;
break; /*遇到空格或制表符忽略*/
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
state_int = TRUE;
suffix[j++] = c; /*遇到数字输出*/
break;
case '(':
if (state_int == TRUE)
suffix[j++] = ' ';/*状态从true转换为false时输出一个空格*/
state_int = FALSE;
push_seq(ps, c); /*遇到左括号，入栈*/
break;
case ')':
if (state_int == TRUE)
suffix[j++] = ' ';/*状态从true转换为false时输出一个空格*/
state_int = FALSE;
c2 = ')';
while (!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);/*取栈顶*/
pop_seq(ps); /*出栈*/
if (c2 == '(')
{
break;
}
suffix[j++] = c2;
}
if (c2 != '(')
{
free(ps);
suffix[j++] = '\0';
return FALSE;
}
break;
case '+':
case '-':
if (state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if (c2 == '+' || c2 == '-' || c2 == '*' || c2 == '/')
{
pop_seq(ps);
suffix[j++] = c2;
}
else if(c2=='(') break;
}
push_seq(ps, c);
break;
case '*':
case '/':
if (state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
while (!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if (c2 == '*' || c2 == '/')
{
pop_seq(ps);
suffix[j++] = c2;
}
else if(c2=='+'||c2=='-'||c2=='(') break;
}
push_seq(ps, c);
break;
default:
free(ps);
suffix[j++] = '\0';
return FALSE;
}
}
if (state_int == TRUE) suffix[j++] = ' ';
while (!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
pop_seq(ps);
if (c2 == '(')
{
free(ps);
suffix[j++] = '\0';
return FALSE;
}
suffix[j++] = c2;
}
free(ps);
suffix[j++] = '\0';
return TRUE;
} int calculateSuffix(const char * suffix, int * presult)
{

int state_int = FALSE;
PSeqStack ps = createEmptyStack_seq();
int num = 0, num1, num2;
int i;
char c;
for (i = 0; suffix[i] != '\0'; i++)
{
c = suffix[i];
switch (c)
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
if (state_int == TRUE)
num = num * 10 + c - '0';
else num = c - '0';
state_int = TRUE;
break;
case ' ':
case'\t':
case '\n':
if (state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
break;
case '+':
case '-':
case '*':
case '/':
if (state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
if (isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
num2 = top_seq(ps);
pop_seq(ps);
if (isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
num1 = top_seq(ps);
pop_seq(ps);
if (c == '+')
push_seq(ps, num1 + num2);
if (c == '-')
push_seq(ps, num1 - num2);
if (c == '*')
push_seq(ps, num1 * num2);
if (c == '/')
push_seq(ps, num1 / num2);
break;
default:
free(ps);
return FALSE;
}
}
*presult = top_seq(ps);
pop_seq(ps);
if (!isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
free(ps);
return TRUE;
} void getline(char * line, int limit)
{
char c;
int i = 0;
while (i < limit - 1 && (c = getchar()) != EOF && c != '\n')
line[i++] = c;
line[i] = '\0';
} void main()
{ char c, infix[MAXNUM], suffix[MAXNUM];
int result;
int flag = TRUE;
while (flag == TRUE)
{
printf("Plese input an infix expression!\nInput:");
getline(infix, MAXNUM);
if(infixtoSuffix(infix, suffix) == TRUE)
printf("suffix:%s\n", suffix);
else
{
printf("Invalid infix!\n");
printf("\nContinue? (y/n)");
scanf("%c", &c);
if (c == 'n' || c == 'N') flag = FALSE;
while (getchar() != '\n');
printf("\n");
continue;
}
if(calculateSuffix(suffix, &result) == TRUE)
printf("Result:%d\n", result);
else
printf("Invalid suffix!\n");
printf("\nContinue? (y/n)");
scanf("%c", &c);
if (c == 'n' || c == 'N') flag = FALSE;
while (getchar() != '\n');
printf("\n");
}
}