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

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

数据结构

开发平台：

C/C++

5_7.C：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 5_7.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;             /* 运算子栈指标      */
  17. /* ---------------------------------------- */
  18. /*  栈资料的存入                          */
  19. /* ---------------------------------------- */
  20. link push(link stack,int value)
  21. {
  22.    link new_node;                 /* 新节点指标          */
  24.    /* 配置节点记忆体 */
  25.    new_node = ( link ) malloc(sizeof(stack_list));
  26.    if ( !new_node )
  27.    {
  28.       printf("记忆体配置失败! n");
  29.       return NULL;                /* 存入失败            */
  30.    }
  31.    new_node->data = value;        /* 建立节点内容        */
  32.    new_node->next = stack;        /* 新节点指向原开始    */
  33.    stack = new_node;              /* 新节点成为栈开始  */
  34.    return stack;
  35. }
  37. /* ---------------------------------------- */
  38. /*  栈资料的取出                          */
  39. /* ---------------------------------------- */
  40. link pop(link stack,int *value)
  41. {
  42.    link top;                      /* 指向栈顶端        */
  44.    if ( stack != NULL )
  45.    {
  46.       top = stack;                /* 指向栈顶端        */
  47.       stack = stack->next;        /* 栈指标指向下节点  */
  48.       *value = top->data;         /* 取出资料            */
  49.       free(top);                  /* 释回节点记忆体      */
  50.       return stack;               /* 传回栈指标        */
  51.    }
  52.    else
  53.       *value = -1;
  54. }
  56. /* ---------------------------------------- */
  57. /*  检查栈是否是空的                      */
  58. /* ---------------------------------------- */
  59. int empty(link stack)
  60. {
  61.    if ( stack == NULL )           /* 是否是空            */
  62.       return 1;                   /* 空的                */
  63.    else
  64.       return 0;                   /* 不是空的            */
  65. }
  67. /* ---------------------------------------- */
  68. /*  运算子                                  */
  69. /* ---------------------------------------- */
  70. int isoperator(char op)
  71. {
  72.    switch ( op )
  73.    {
  74.       case '(':
  75.       case ')':
  76.       case '+':
  77.       case '-':
  78.       case '*':
  79.       case '/': return 1;         /* 是运算子            */
  80.       default:  return 0;         /* 不是运算子          */
  81.    }
  82. }
  84. /* ---------------------------------------- */
  85. /*  运算子的优先权                          */
  86. /* ---------------------------------------- */
  87. int priority(char op)
  88. {
  89.    switch ( op )
  90.    {
  91.       case '*':
  92.       case '/': return 3;
  93.       case '+':
  94.       case '-': return 2;
  95.       case '(': return 1;
  96.       default:  return 0;
  97.    }
  98. }
  100. /* ---------------------------------------- */
  101. /*  主程式: 输入中序表达式后, 转成后序.     */
  102. /* ---------------------------------------- */
  103. void main()
  104. {
  105.    char infix[100];               /* 中序表达式字符串      */
  106.    char result[100];              /* 结果表达式字符串      */
  107.    int op = 0;                    /* 运算子变数          */
  108.    int pos = 0;                   /* 目前表达式位置      */
  109.    int rpos = 0;                  /* 结果表达式位置      */
  111.    printf("请输入中序表达式 ==> ");
  112.    gets(infix);                   /* 读取表达式          */
  113.    while ( infix[pos] != '' && infix[pos] != 'n' )
  114.    {
  115.       if ( isoperator(infix[pos]) ) /* 是不是运算子      */
  116.       {
  117.          if ( empty(operator) || infix[pos] == '(' )
  118.             /* 存入运算子至栈 */
  119.             operator = push(operator,infix[pos]);
  120.          else
  121.          {
  122.             if ( infix[pos] == ')' ) /* 处理括号         */
  123.             {
  124.                while ( operator->data != '(' )
  125.                {
  126.                   /* 取出运算子直到是'(' */
  127.                   operator = pop(operator,&op);
  128.                   result[rpos++] = op; /* 存入结果表达式 */
  129.                }
  130.                /* 取出运算子'(' */
  131.                operator = pop(operator,&op);
  132.             }
  133.             else
  134.             {
  135.                /* 比较优先权 */
  136.                while ( priority(infix[pos]) <=
  137.                        priority(operator->data) &&
  138.                        !empty(operator) )
  139.                {
  140.                   /* 取出运算子 */
  141.                   operator = pop(operator,&op);
  142.                   result[rpos++] = op; /* 存入结果表达式 */
  143.                }
  144.                /* 存入运算子至栈 */
  145.                operator = push(operator,infix[pos]);
  146.             }
  147.          }
  148.       }
  149.       else
  150.          result[rpos++] = infix[pos];  /* 存入结果表达式 */
  151.       pos++;
  152.    }
  153.    while ( !empty(operator) )        /* 取出剩下的运算子 */
  154.    {
  155.       operator = pop(operator,&op);    /* 取出运算子     */
  156.       result[rpos++] = op;             /* 存入结果表达式 */
  157.    }
  158.    result[rpos] = '';                /* 设定字符串结束   */
  159.    printf("后序表达式是 %sn",result);
  160. }