中缀式转换后缀式的例子

在看堆栈的时候，看到堆栈应用中有一个中缀式转换后缀式，于是自己写了一个。

#include<stdio.h>
#include<stdlib.h>

#define TRUE  1
#define FALSE 0

typedef struct Node
{
    char data;
    struct Node *next;
}LinkStackNode,*LinkStack;

//初始化
void InitStack(LinkStack *S)
{
    *S=(LinkStack)malloc(sizeof(LinkStackNode));
    (*S)->next=NULL;
}
//判断是否为空
int Isempty(LinkStack S)
{
    if(S->next==NULL)
        return TRUE;
    else
        return FALSE;
}
//进栈操作
int Push(LinkStack S,char c)
{
    LinkStackNode *temp;
    temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
    if(temp)
    {
        temp->data=c;
        temp->next=S->next;
        S->next=temp;
        return TRUE;
    }
    else
        return FALSE;
}

//出栈操作

int Pop(LinkStack S,char *c)
{
    LinkStackNode *temp;
    temp=S->next;
    if(temp)
    {
        *c=temp->data;
           S->next=temp->next;
        free(temp);
        return TRUE;
    }
    else
        return FALSE;
}

//取得栈顶指针
int Gettop(LinkStack S,char *c)
{
    LinkStackNode *temp;
    temp=S->next;
    if(temp)
    {
        *c=temp->data;
        return *c;
    }
    else
        return FALSE;
}

void Print(LinkStack S)
{
    LinkStackNode *temp;
    temp=S->next;
    while(temp)
    {
        printf("%c",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
int Match(char a,char b)
{
    if(a=='('&&b==')')
        return TRUE;
    else if(a=='['&&b==']')
        return TRUE;
    else if(a=='{'&&b=='}')
        return TRUE;
    else
        return FALSE;
}
void BreakMatch(char *str)
{
    LinkStack S;
    int i;
    char ch;
    InitStack(&S);
    for(i=0;str[i]!='\0';i++)
    {
        switch(str[i])
        {
            case '(':
            case '[':
            case '{':
                Push(S,str[i]);
                break;
            case ')':
            case ']':
            case '}':
                if(Isempty(S))
                {
                    printf("\n右括号多余!\n");
                    return;
                }
                else
                {
                    Gettop(S,&ch);
                    if(Match(ch,str[i]))
                        Pop(S,&ch);
                    else
                    {
                        printf("\n对应的左右括号不是同类!\n");
                        return;
                    }
                }

        }
    }
    if(Isempty(S))
        printf("\n括号匹配!\n");
    else
        printf("\n左括号多余!\n");

}
void  Mid_end(LinkStack S,int n)
{
    char ch,sh;
    char s[30];
    int i=0;
    LinkStack L;
    InitStack(&L);
    while(S||L)
    {
        if(S)
            Gettop(S,&ch);
        switch(ch)
        {
            case '+':
            case '-':
            case '*':
            case '/':
            case '(':
                Push(L,ch);
                Pop(S,&ch);
                break;
            case ')':
                Pop(S,&ch);
                while(L->next!=NULL)
                {
                    Gettop(L,&ch);
                    if(ch=='(')
                    {
                        Pop(L,&ch);
                        while(S->next==NULL&&L->next!=NULL)
                        {
                            Gettop(L,&ch);
                            printf("%c",ch);
                            Pop(L,&ch);
                        }

                        break;
                    }
                    printf("%c",ch);
                    Pop(L,&ch);
                }
                break;
            default:
                Gettop(S,&ch);
                printf("%c",ch);
                Pop(S,&ch);
                while(S->next==NULL&&L->next!=NULL)
                {
                    Gettop(L,&ch);
                    printf("%c",ch);
                    Pop(L,&ch);
                }
                break;
        }
        if(S->next==NULL&&L->next==NULL)
            break;
    }
    printf("\n");
}
int main()
{
    LinkStack S;
    char ch;
    int i;
    int n;
    InitStack(&S);
    printf("please input the string you want:");
    for(i=0;i<30;i++)
    {
        ch=getchar();
        if(ch=='#')
            break;
        Push(S,ch);
        i++;
    }
    n=i;
    Mid_end(S,n);
//    BreakMatch(str);
}

问题是：由于堆栈的先进后出，所以在输入的时候我都是反着输入的
eg:A+(B-C/D)*E#
我在输入的时候都是E*）D/C-B（+A#来输入的
——————————————————————————————————
对于一个堆栈 输入ABC，输出的所有选项有
A进A出，B进B出，C进C出（顺序是ABC）
A进B进，B出C进，C出A出（顺序是BCA）
A进B进，C进，C出B出A出（顺序是CBA）
A进A出，B进C进，C出B出（顺序是ACB）
A进B进，B出A出，C进C出（顺序是BAC）
就是不可能为CAB