从中缀向后缀转换表达式

问题描述 　　中缀表达式就是我们通常所书写的数学表达式，后缀表达式也称为逆波兰表达式，在编译程序对我们书写的程序中的表达式进行语法检查时，往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的算术表达式转换成后缀表示，例如，将中缀表达式 (A 一 (B*C 十 D)*E) ／ (F 十 G ) 转换为后缀表示为： ABC*D十E*—FG十／ 注意：为了简化编程实现，假定变量名均为单个字母，运算符只有＋，－，＊，／ 和＾（指数运算），可以处理圆括号（），并假定输入的算术表达式正确。 要求：使用栈数据结构实现 ，输入的中缀表达式以＃号结束 输入 整数N。表示下面有N个中缀表达式 N个由单个字母和运算符构成的表达式 输出 N个后缀表达式。

#include
#include 
#include 
#define Error（ Str ）        FatalError（ Str ）
#define FatalError（ Str ）   fprintf（ stderr “%s\n“ Str ） exit（ 1 ）

/* START: fig3_39.txt */
        #ifndef _Stack_h
        #define _Stack_h

		typedef int ElementType;
		struct Node;
        typedef struct Node *PtrToNode;
        typedef PtrToNode Stack;

        int IsEmpty（ Stack S ）;
        Stack CreateStack（ int MaxElements ）;
        void DisposeStack（ Stack S ）;
        void MakeEmpty（ Stack S ）;
        void Push（ ElementType X Stack S ）;
        ElementType Top（ Stack S ）;
        void Pop（ Stack S ）;

        #endif  /* _Stack_h */

/* END */

        struct Node
        {
            ElementType Element;
            PtrToNode   Next;
        };

        int
        IsEmpty（ Stack S ）
        {
            return S->Next == NULL;
        }
        Stack
        CreateStack（ int MaxElements ）
        {
            Stack S;

			S = （Stack）malloc（sizeof（struct Node））;
            if（ S == NULL ）
                FatalError（ “Out of space!!!“ ）;
            S->Next = NULL;
            return S;
        }

        void
        MakeEmpty（ Stack S ）
        {
            if（ S == NULL ）
                Error（ “Must use CreateStack first“ ）;
            else
                while（ !IsEmpty（ S ） ）
                    Pop（ S ）;
        }

        void
        DisposeStack（ Stack S ）
        {
            MakeEmpty（ S ）;
            free（ S ）;
        }

        void
        Push（ ElementType X Stack S ）
        {
            PtrToNode TmpCell;

            TmpCell = （PtrToNode）malloc（ sizeof（ struct Node ） ）;
            if（ TmpCell == NULL ）
                FatalError（ “Out of space!!!“ ）;
            else
            {
                TmpCell->Element = X;
                TmpCell->Next = S->Next;
                S->Next = TmpCell;
            }
        }
        ElementType
        Top（ Stack S ）
        {
            if（ !IsEmpty（ S ） ）
                return S->Next->Element;
            Error（ “Empty stack“ ）;
            return 0;  /* Return value used to avoid warning */
        }
        void
        Pop（ Stack S ）
        {
            PtrToNode FirstCell;

            if（ IsEmpty（ S ） ）
                Error（ “Empty stack“ ）;
            else
            {
                FirstCell = S->Next;