利用栈实现:中缀表达式转后缀表达式
题目:现有中缀表达式如:1+(2-3)*4+10/5
请用栈的特性编写一个程序,使得程序输出后缀表达式
分析如下:
STEP1:
1+(2-3)*4+10/5
首先遇到第一个输入是数字1,数字在后缀表达式中都是直接输出,接着是符号“+”,入栈:
STEP2:
1+(2-3)*4+10/5
第三个字符是“(”,依然是符号,入栈,接着是数字2,输出,然后是符号“-”,入栈:
STEP3:
1+(2-3)*4+10/5
接下来是数字3,输出,紧跟着是“)”,此时,我们需要去匹配栈里的“(”,然后再匹配前将栈顶数据依次出栈(这就好比括号里优先执行的道理):
STEP4:
1+(2-3)*4+10/5
紧接着是符号“*”,直接入栈
STEP5:
1+(2-3)*4+10/5
遇到数字4,输出,之后是符号“+”,此时栈顶元素是符号“*”,按照先乘除后加减原理,此时栈顶的乘号优先级比即将入栈的加好要大,所以出栈。
栈中第二个元素是加号,按理来说大家平起平坐,但是按照先来后到的原则,栈里的加号呆得太久了,也要出栈透透气。(同理如果栈里还有其他操作符,也是出栈)
最后把刚刚的那个加号入栈,操作如下图:
STEP6:
1+(2-3)*4+10/5
紧接着数字10,输出,最后是符号“/”,进栈:
STEP7:
1+(2-3)*4+10/5
最后一个数字5,输出,所有的输入处理完毕,但是栈中仍然有数据,所以将栈中符号依次出栈。
总结规则:
从左到右遍历中缀表达式的每个数字和符号,若是数字则直接输出,若是符号,则判断其与栈顶符号的优先级,是右括号或者优先级低于栈顶符号,则栈顶元素依次出栈并输出,直到遇到左括号或栈空才将低优先级的那个符号入栈
代码实现如下:
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
InitStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if( !s->base )
exit(0);
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
}
Push(sqStack *s, ElemType e)
{
// 栈满,追加空间,鱼油必须懂!
if( s->top - s->base >= s->stackSize )
{
s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base )
exit(0);
s->top = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
*(s->top) = e; // 存放数据
s->top++;
}
Pop(sqStack *s, ElemType *e)
{
if( s->top == s->base )
return;
*e = *--(s->top); // 将栈顶元素弹出并修改栈顶指针
}
int StackLen(sqStack s)
{
return (s.top - s.base);
}
int main()
{
sqStack s;
char c, e;
InitStack( &s );
printf("请输入中缀表达式,以#作为结束标志:");
scanf("%c", &c);
while( c != '#' )
{
while( c>='0' && c<='9' )
{
printf("%c", c);
scanf("%c", &c);
if( c<'0' || c>'9' )
{
printf(" ");
}
}
if( ')' == c )
{
Pop(&s, &e);
while( '(' != e )
{
printf("%c ", e);
Pop(&s, &e);
}
}
else if( '+'==c || '-'==c )
{
if( !StackLen(s) )
{
Push(&s, c);
}
else
{
do
{
Pop(&s, &e);
if( '(' == e )
{
Push(&s, e);
}
else
{
printf("%c ", e);
}
}while( StackLen(s) && '('!=e );
Push(&s, c);
}
}
else if( '*'==c || '/'==c || '('==c )
{
Push(&s, c);
}
else if( '#'== c )
{
break;
}
else
{
printf("\n出错:输入格式错误!\n");
return -1;
}
scanf("%c", &c);
}
while( StackLen(s) )
{
Pop(&s, &e);
printf("%c ", e);
}
return 0;
}