数据结构

开发平台：
C/C++

5_5.C：源码内容
							/* ======================================== */
/*    程式实例: 5_5.c                     */
/*    前序四则表达式的值                    */
/* ======================================== */
#include <stdlib.h>
struct stack_node                 /* 栈的结构宣告     */
{
   int data;                      /* 栈资料           */
   struct stack_node *next;       /* 指向下一节点       */
};
typedef struct stack_node stack_list; /* 串列新型态     */
typedef stack_list *link;             /* 串列指标新型态 */
link prefix  = NULL;              /* 表达式栈指标     */
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;                   /* 目前表达式位置     */
   int token = 0;                 /* 运算子或运算元     */
   printf("请输入前序表达式 ==> ");
   gets(exp);                     /* 读取表达式         */
   printf("前序表达式[%s]的结果是 ",exp);
   /* 将表达式存入栈 */
   while ( exp[pos] != '' && exp[pos] != 'n' )
   {
      prefix = push(prefix,exp[pos]);
      pos++;                      /* 下一字符串位置       */
   }
   /* 剖析表达式字符串回路 */
   while ( !empty(prefix) )
   {
      prefix = pop(prefix,&token); /* 取出一元素        */
      if ( isoperator(token) )    /* 是不是运算子       */
      {
         /* 从栈取出两运算元 */
         operand = pop(operand,&operand1);
         operand = pop(operand,&operand2);
         /* 计算取出运算子和元的值后, 存入栈 */
         operand = push(operand,
                        get_value(token,operand2,operand1));
      }
      else
         /* 是运算元, 存入运算元栈 */
         operand = push(operand,token-48);
   }
   operand = pop(operand,&result); /* 取出结果          */
   printf(" %dn",result);        /* 印出结果           */
}

						