/* ======================================== */
/*    程式實例:5_6.c                     */
/*    后序四則表達式的值                    */
/* ======================================== */
#include <stdlib.h>

struct stack_node                 /* 棧的結構宣告     */
{
   int data;                      /* 棧資料           */
   struct stack_node *next;       /* 指向下一節點       */
};
typedef struct stack_node stack_list; /* 串列新型態     */
typedef stack_list *link;         /* 串列指標新型態     */

link operand  = NULL;             /* 運算元棧指標     */

/* ---------------------------------------- */
/*  棧資料的存入                          */
/* ---------------------------------------- */
link push(link stack,int value)
{
   link new_node;                 /* 新節點指標         */

   /* 配置節點記憶體 */
   new_node = ( link ) malloc(sizeof(stack_list));
   if ( !new_node )
   {
      printf("記憶體配置失敗! \n");
      return NULL;                /* 存入失敗           */
   }
   new_node->data = value;        /* 建立節點內容       */
   new_node->next = stack;        /* 新節點指向原開始   */
   stack = new_node;              /* 新節點成為棧開始 */
   return stack;
}

/* ---------------------------------------- */
/*  棧資料的取出                          */
/* ---------------------------------------- */
link pop(link stack,int *value)
{
   link top;                      /* 指向棧頂端       */

   if ( stack != NULL )
   {
      top = stack;                /* 指向棧頂端       */
      stack = stack->next;        /* 棧指標指向下節點 */
      *value = top->data;         /* 取出資料           */
      free(top);                  /* 釋回節點記憶體     */
      return stack;               /* 傳回棧指標       */
   }
   else
      *value = -1;
}

/* ---------------------------------------- */
/*  檢查棧是否是空的                      */
/* ---------------------------------------- */
int empty(link stack)
{
   if ( stack == NULL )           /* 是否是空           */
      return 1;                   /* 空的               */
   else
      return 0;                   /* 不是空的           */
}

/* ---------------------------------------- */
/*  是否是運算子                            */
/* ---------------------------------------- */
int isoperator(char op)
{
   switch ( op )
   {
      case '+':
      case '-':
      case '*':
      case '/': return 1;         /* 是運算子           */
      default:  return 0;         /* 不是運算子         */
   }
}

/* ---------------------------------------- */
/*  計算二元表達式的值                      */
/* ---------------------------------------- */
int get_value(int op,int operand1,int operand2)
{
   switch ( (char) op )
   {
      case '*': return ( operand2 * operand1 );
      case '/': return ( operand2 / operand1 );
      case '+': return ( operand2 + operand1 );
      case '-': return ( operand2 - operand1 );
   }
}

/* ---------------------------------------- */
/*  主程式: 輸入后序表達式后, 計算其值.     */
/* ---------------------------------------- */
void main()
{
   char exp[100];                 /* 表達式字符串變數     */
   int operand1 = 0;              /* 前運算元變數       */
   int operand2 = 0;              /* 后運算元變數       */
   int result = 0;                /* 計算結果變數       */
   int pos = 0;                   /* 目前表達式位置     */

   printf("請輸入后序表達式 ==> ");
   gets(exp);                     /* 讀取表達式         */
   printf("后序表達式[%s]的結果是 ",exp);
   /* 剖析表達式字符串回路 */
   while ( exp[pos] != '\0' && exp[pos] != '\n' )
   {
      if ( isoperator(exp[pos]) ) /* 是不是運算子       */
      {
         /* 從棧取出一運算子和兩運算元 */
         operand = pop(operand,&operand1);
         operand = pop(operand,&operand2);
         /* 計算取出運算子和元的值后, 存入棧 */
         operand = push(operand,
                        get_value(exp[pos],operand1,operand2));
      }
      else
         /* 是運算元, 存入運算元棧 */
         operand = push(operand,exp[pos]-48);
      pos++;                      /* 下一字符串位置       */
   }
   operand = pop(operand,&result); /* 取出結果          */
   printf(" %d\n",result);        /* 印出結果           */
}