开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 数据结构 > 查看源码
5_4.C
资源名称：04722-x　[点击查看]
上传用户：wyn840322
上传日期：2007-01-13
资源大小：294k
文件大小：5k
源码类别：

数据结构

开发平台：

C/C++

5_4.C：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 5_4.c                     */
  3. /*    中序四则表达式的值                    */
  4. /* ======================================== */
  5. #include <stdlib.h>
  7. struct stack_node                 /* 栈的结构宣告     */
  8. {
  9.    int data;                      /* 栈资料           */
  10.    struct stack_node *next;       /* 指向下一节点       */
  11. };
  12. typedef struct stack_node stack_list;  /* 串列新型态    */
  13. typedef stack_list *link;         /* 串列指标新型态     */
  15. link operator = NULL;             /* 运算子栈指标     */
  16. link operand  = NULL;             /* 运算元栈指标     */
  18. /* ---------------------------------------- */
  19. /*  栈资料的存入                          */
  20. /* ---------------------------------------- */
  21. link push(link stack,int value)
  22. {
  23.    link new_node;                 /* 新节点指标         */
  25.    /* 配置节点记忆体 */
  26.    new_node = ( link ) malloc(sizeof(stack_list));
  27.    if ( !new_node )
  28.    {
  29.       printf("记忆体配置失败! n");
  30.       return NULL;                /* 存入失败           */
  31.    }
  32.    new_node->data = value;        /* 建立节点内容       */
  33.    new_node->next = stack;        /* 新节点指向原开始   */
  34.    stack = new_node;              /* 新节点成为栈开始 */
  35.    return stack;
  36. }
  38. /* ---------------------------------------- */
  39. /*  栈资料的取出                          */
  40. /* ---------------------------------------- */
  41. link pop(link stack,int *value)
  42. {
  43.    link top;                      /* 指向栈顶端       */
  45.    if ( stack != NULL )
  46.    {
  47.       top = stack;                /* 指向栈顶端       */
  48.       stack = stack->next;        /* 栈指标指向下节点 */
  49.       *value = top->data;         /* 取出资料           */
  50.       free(top);                  /* 释回节点记忆体     */
  51.       return stack;               /* 传回栈指标       */
  52.    }
  53.    else
  54.       *value = -1;
  55. }
  57. /* ---------------------------------------- */
  58. /*  检查栈是否是空的                      */
  59. /* ---------------------------------------- */
  60. int empty(link stack)
  61. {
  62.    if ( stack == NULL )           /* 是否是空           */
  63.       return 1;                   /* 空的               */
  64.    else
  65.       return 0;                   /* 不是空的           */
  66. }
  68. /* ---------------------------------------- */
  69. /*  是否是运算子                            */
  70. /* ---------------------------------------- */
  71. int isoperator(char op)
  72. {
  73.    switch ( op )
  74.    {
  75.       case '+':
  76.       case '-':
  77.       case '*':
  78.       case '/': return 1;         /* 是运算子           */
  79.       default:  return 0;         /* 不是运算子         */
  80.    }
  81. }
  83. /* ---------------------------------------- */
  84. /*  运算子的优先权                          */
  85. /* ---------------------------------------- */
  86. int priority(char op)
  87. {
  88.    switch ( op )
  89.    {
  90.       case '*':
  91.       case '/': return 2;
  92.       case '+':
  93.       case '-': return 1;
  94.       default:  return 0;
  95.    }
  96. }
  98. /* ---------------------------------------- */
  99. /*  计算二元表达式的值                      */
  100. /* ---------------------------------------- */
  101. int get_value(int op,int operand1,int operand2)
  102. {
  103.    switch ( (char) op )
  104.    {
  105.       case '*': return ( operand2 * operand1 );
  106.       case '/': return ( operand2 / operand1 );
  107.       case '+': return ( operand2 + operand1 );
  108.       case '-': return ( operand2 - operand1 );
  109.    }
  110. }
  112. /* ---------------------------------------- */
  113. /*  主程式: 输入中序表达式后, 计算其值.     */
  114. /* ---------------------------------------- */
  115. void main()
  116. {
  117.    char exp[100];                 /* 表达式字符串变数     */
  118.    int op = 0;                    /* 运算子变数         */
  119.    int operand1 = 0;              /* 前运算元变数       */
  120.    int operand2 =0;               /* 后运算元变数       */
  121.    int result = 0;                /* 计算结果变数       */
  122.    int pos = 0;                   /* 目前表达式位置     */
  124.    printf("请输入中序表达式 ==> ");
  125.    gets(exp);                     /* 读取表达式         */
  126.    /* 剖析表达式字符串回路 */
  127.    while ( exp[pos] != '' && exp[pos] != 'n' )
  128.    {
  129.       if ( isoperator(exp[pos]) ) /* 是不是运算子       */
  130.       {
  131.          if ( !empty(operator) )  /* 检查运算子栈     */
  132.             while ( priority(exp[pos]) <=  /* 比较优先权回路 */
  133.                     priority(operator->data) &&
  134.                     !empty(operator) )
  135.             {
  136.                /* 从栈取出一运算子和两运算元 */
  137.                operator = pop(operator,&op);
  138.                operand = pop(operand,&operand1);
  139.                operand = pop(operand,&operand2);
  140.                /* 计算取出运算子和元的值后, 存入栈 */
  141.                operand = push(operand,
  142.                          get_value(op,operand1,operand2));
  143.             }
  144.          /* 是运算子, 存入运算子栈 */
  145.          operator = push(operator,exp[pos]);
  146.       }
  147.       else
  148.          /* 是运算元, 存入运算元栈 */
  149.          operand = push(operand,exp[pos]-48);
  150.       pos++;                      /* 下一字符串位置       */
  151.    }
  152.    /* 取出运算子栈的全部内容 */
  153.    while ( !empty(operator) )
  154.    {
  155.       /* 从栈取出一运算子和两运算元 */
  156.       operator = pop(operator,&op);
  157.       operand = pop(operand,&operand1);
  158.       operand = pop(operand,&operand2);
  159.       /* 计算取出运算子和元的值后, 存入栈 */
  160.       operand = push(operand,get_value(op,operand1,operand2));
  161.    }
  162.    operand = pop(operand,&result);     /* 取出结果      */
  163.    printf("表达式[%s]的结果是 %dn",exp,result);
  164. }