论坛 › 数据结构与算法 › 中缀表达式转化为后缀表达式

山小鸡 发表于 2014-2-28 19:46:22

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

中缀表达式转化为后缀表达式，程序编译时没错，当时运行时结果不对，我自己查了好久也是没结果，希望热心鱼油能帮助我一哈

#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;

void 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;
}

void 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 += STACKINCREMENT;
        }
       
        *(s->top) = e;                //储存数据
        s->top++;
}

void 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(void)
{
        sqStack s;
        char c,e;

        InitStack(&s);
       
        printf("请输入中中缀表达式，以#作为结束的标志：\n");
        scanf("%c",&c);
       
        while(c != '#')
        {
                while(c>='0' && c<='9')
                {
                       printf("%c",c);
                       scanf("%c",&c);
                       if(c<'0'|| c>'9')
                       {
                               printf(" ");
                       }
                }
               
                if(')' == c)                //c == '('这样写防止bug出现
                {
                        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");
                        return -1;               
                }
               
                scanf("%c",c);
        }
       
        while(StackLen(s))
        {
                Pop(&s,&e);
                printf("%c",e);        
        }
        return 0;       
}

查看完整版本: 中缀表达式转化为后缀表达式