中缀表达式转换为后缀表达式

Q1：把中缀表达式转化为后缀表达式的源程序

中缀表达式转化成后缀表达式并求值的算法 #include
#include
#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 == nc == 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 == nc == N) flag = FALSE;
while (getchar() != \n);
printf("\n");
}
}

wWW.YiJiTA‖O.COm

Q2：求助教程，把中缀表达式转换为后缀表达式的算法

include "stdio.h"
#include "stdlib.h"
#include "string.h" #define MaxStackSize100 #define M 100 typedef char DataType;#include "SeqStack.h"#include "implement.c" /////////////////////////////计算表达式/////////////////////////////////
void EvaluateExpression(char *exp)
{
char c;
char theta;
char tmpc,a,b,y;
//char x,ch; SeqStack OPTR;//运算符栈
SeqStack OPND;//操作数栈 //int s1,s2; StackInitiate(&OPTR);
StackPush(&OPTR,#); StackInitiate(&OPND);
c=*exp++; //printf("当前读取的字符为%c\n",c);
StackTop(OPTR,&tmpc); //printf("当前运算符栈顶字符为%c\n",tmpc);
//printf("%c",tmpc); while (c!=#tmpc!=#)
{
printf("进入循环，当前读取表达式的字符为%c\n",c); if(!IsOperator(c))//如果获取的字符不是运算符则入操作数栈
{
printf("发现操作数\n");
StackPush(&OPND,c);
c=*exp++; //x=getchar();
}
else
{
printf("发现运算符\n"); //StackTop(OPTR,&tmpc);//获取当前运算符栈顶字符 //printf("当前的运算符是：%c\n",tmpc);
//ch=Precede(tmpc,c);
//printf("运算符是：%c\n",ch); switch(Precede(tmpc,c))
{
case <://栈顶元素优先权低
StackPush(&OPTR,c); //c=*exp++;
//printf("栈顶元素优先级低：入栈\n");
//printf("%c",tmpc);
break;
case =://脱括号
//StackPop(&OPTR,&tmpc);
//printf("左右括号匹配！"); //StackTop(OPTR,&tmpc);//获取脱括号后的当前运算符栈顶，继续和此时读取的运算符比较
break; case >://退栈并计算
//printf("栈顶元素优先级高：出栈\n");
StackPop(&OPTR,&theta); //printf("当前进行的运算是:");
//printf("%c\n",theta);
StackPop(&OPND,&b); StackPop(&OPND,&a);
StackPush(&OPND, Operate(a,theta,b));
StackTop(OPTR,&theta);//获取一个运算符出栈之后的当前运算符栈顶，继续和此时读取的运算符比较 while(Precede(theta,c)==>)
{ StackPop(&OPND,&b); StackPop(&OPND,&a);
StackPush(&OPND, Operate(a,theta,b));StackPop(&OPTR,&theta);//将当前的栈顶弹出（刚刚比较过的运算符）
StackTop(OPTR,&theta);//获取当前新的栈顶
} if(Precede(theta,c)===)//右括号始终不进栈，在此去除左括号。
{
StackPop(&OPTR,&theta);//将当前的栈顶弹出（刚刚比较过的运算符）
//StackTop(OPTR,&theta);//获取当前新的栈顶
}
if(c!=#&&c!=))//将所有栈内优先级高的运算完成（出栈）之后，将当前的运算符入栈
StackPush(&OPTR,c);
//StackTop(OPND,&y);
//printf("当前操作数栈顶为%c\n",y);
//c=*exp++;
break;
}//switch if(!StackEmpty(OPTR))
StackTop(OPTR,&tmpc); //if(tmpc==#) break;
//x=getchar(); if(c!=#)
c=*exp++;//c指向下一个字符
}
//printf("in while");
//printf("当前的theta：%c\n",theta);
//printf("当前的c：%c\n",c);
//printf("当前的tmpc：%c\n",tmpc); }//while
StackTop(OPND,&y);
printf("表达式的运算结果为%c\n",y);
} void main(void)
{ char str[M];
printf("请输入中缀表达式（注意所有运算结果都应该保证在10以内，以免出错.）：\n");
gets(str);
EvaluateExpression(str);
}

Q3：如何在程序中将中缀表达式转换为后缀表达式

中缀表达式转换为后缀表达式的方法
a + b * c - (d + e)
按照运算符的优先级对所有的运算单位加括号。
((a + (b * c)) - (d + e))
转换中缀与后缀表达式后缀：把运算符号移动到对应的括号后面。
((a (b c) * ) + (d e) + ) -
把括号去掉，记得到了后缀表达式
a b c * + d e + -
可以发现，后缀表达式是不需要括号来调整运算优先级的。

wWw..YIJITao.coM

Q4：表达式求值 中缀表达式转换为后缀表达式流程图

我们在数学中常见的计算式，例如2+（3*4）叫做中缀表达式。表达式中涉及到了多个运算符，而运算符之间是有优先级的。计算机在计算并且处理这种表达式时，需要将中缀表达式转换成后缀表达式，然后再进行计算。 中缀表达式转后缀表达式遵循以下原则： 1.遇到操作数，直接输出； 2.栈为空时，遇到运算符，入栈； 3.遇到左括号，将其入栈；
4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；
5.遇到其他运算符+-*/时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；
6.最终将栈中的元素依次出栈，输出。
经过上面的步骤，得到的输出既是转换得到的后缀表达式。

Q5：中缀表达式如何转换为前后缀表达式？

1、中缀表达式变后缀的算法：遇到操作数，直接输出。

2、栈为空是，遇到运算符，直接入栈。

3、遇到左括号时，将其入栈。

4、遇到右括号时，执行出栈操作，并且开始将出栈的元素输出。直到弹出栈的元素是左括号为止。

5、遇到其他运算符的时候，弹出所有优先级大于等于该运算符栈顶元素，然后将该运算符入栈。最终将栈中的元素依次出栈。

Q6：中缀表达式怎么转换为后缀表达式

1. 初始化一空栈，用来对符号进出栈使用。
2. 第一个字符是数字9，输出9，后面是符号“+”，进栈。
3. 第三个字符是“(”,依然是符号，因其只是左括号，还未配对，故进栈。
4. 第四个字符是数字3，输出，总表达式为9 3,接着是“-”进栈。
5. 接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”，总的输出表达式为9 3 1 -
6. 接着是数字3，输出，总的表达式为9 3 1 - 3 。紧接着是符号“*”，因为此时的栈顶符号为“+”号，优先级低于“*”，因此不输出，进栈。
7. 之后是符号“+”，此时当前栈顶元素比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为 9 3 1 - 3 * +.然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”，而下图中的栈底（也是栈顶）的“+”是指“9+(3-1)*3+”中的最后一个“+”。
8. 紧接着数字10，输出，总表达式变为9 3 1-3 * + 10。
9. 最后一个数字2,输出，总的表达式为 9 3 1-3*+ 10 2、
10. 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+
从刚才的推导中你会发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：
将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
将后缀表达式进行运算得出结果（栈用来进出运算的数字）。
整个过程，都充分利用了找的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。