Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2760516
  • 博文数量: 102
  • 博客积分: 1444
  • 博客等级: 中尉
  • 技术积分: 13891
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-29 10:58
文章分类

全部博文(102)

文章存档

2014年(29)

2013年(14)

2012年(59)

分类: C/C++

2012-03-31 22:26:37

转载请注明来源chengyaogen.blog.chinaunix.net
 
基于栈的表达式计算
思路:
        设计一个运算符栈
        设计一个数据栈
1.输入表达式
eg:
    123 + 3 * 3 - 24
2.分析这个字符串
    观察我们发现,每个数字都是一个字符,那如何 把123三个字符转换成123数字呢
    提示:
    int data = 0;
    data = data * 10 + buf[i] - '0'; 
3.数字和运算符分别入栈
    while(buf[i])
    {
    if(buf[i] >= '0' && buf[i] <= '9')
    {
            收集数据
   }else{//遇到运算符
            
          push_stack_data();
          deal_with();//对运算符处理  
    }
}

观察一下,但遍历这个字符串结束后,最后一个数字是否入栈了。 
      push_stack_data();
      last_deal_with();
__________________________________________________________________________

deal_with:
                1.如果运算符的栈为空,直接将运算符入栈,然后返回  
                2.如果运算符栈不为空,当前的运算符能不能入栈,需要判断.
                3.取出运算符栈顶的运算符和当前运算符进行优先级比较,如果有当前运算符优先级高,直接入栈,然后函数返回,否则calc_data,将计算的结果继续入数据栈,然后继续(注意,如果在操作过程中,运算符栈已经为空,这个时候当前运算符入栈,然后返回)。
            
calc_data:
            从运算符栈中出一个operator,从数据栈中出两个data,然后进行运算,把运算的结果返回。
______________________________________________________________________________

last_deal_with:
    经过我们以上的处理,此时运算符栈中的运算符应该都是同级的,此时我们只要
    while(1)
    {
        if(!is_empty_operator_stack())
        {
                value = calc_data();
                push_data_stack();

        }else{
                break;
        }
    }

这样最终数据栈中放的就是最后的运算结果

主程序从这里开始:
 
 
主体代码:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "datastack.h"
  4. #include "operstack.h"

  5. #define MAX 100

  6. int get_levle(char operator)
  7. {
  8.     int level;
  9.     
  10.     switch(operator)
  11.     {
  12.         case '(':
  13.             level = 0;
  14.             break;
  15.         case '+':
  16.         case '-':
  17.             level = 1;
  18.             break;
  19.         case '*':
  20.         case '/':
  21.             level = 2;
  22.             break;
  23.     }

  24.     return level;
  25. }

  26. int calc_data(DataStack *p,OperatorStack *q)
  27. {
  28.     char operator;
  29.     int data1,data2;
  30.     int value;

  31.     data2 = pop_data_stack(p);
  32.     data1 = pop_data_stack(p);
  33.     operator = pop_operator_stack(q);

  34. #ifndef _DEBUG_
  35.     printf(" %d %c %d\n",data1,operator,data2);
  36. #endif

  37.     switch(operator)
  38.     {
  39.         case '+':
  40.             value = data1 + data2;
  41.             break;

  42.         case '-':
  43.             value = data1 - data2;
  44.             break;

  45.         case '*':
  46.             value = data1 * data2;
  47.             break;

  48.         case '/':
  49.             value = data1 / data2;
  50.             break;
  51.     }

  52.     return value;
  53. }

  54. //1 + 2 * 3 + 4
  55. int deal_with(DataStack *pdata,OperatorStack *poper,char op)
  56. {
  57.     int new_level;
  58.     int old_level;
  59.     int value;
  60.     
  61.     if(is_empty_operator_stack(poper))
  62.     {
  63.             push_operator_stack(poper,op);
  64.             return 0;
  65.     }
  66.     
  67.     while(1)
  68.     {
  69.         new_level = get_levle(op);
  70.         old_level = get_levle(get_stack_top_operator(poper));

  71.         if(new_level > old_level || is_empty_operator_stack(poper))
  72.         {
  73.             push_operator_stack(poper,op);
  74.             return 0;
  75.         
  76.         }else{
  77.             value = calc_data(pdata,poper);
  78.             push_data_stack(pdata,value);
  79.         }

  80.         printf("value = %d\n",value);
  81.     }

  82.     return value;
  83. }

  84. int stack_init(DataStack *pdata,OperatorStack *poper)
  85. {
  86.     init_data_stack(pdata);
  87.     init_operator_stack(poper);

  88.     return 0;
  89. }

  90. int last_deal_with(DataStack *pdata,OperatorStack *poper)
  91. {
  92.     int value;
  93.     
  94.     while(1)
  95.     {
  96.         if(!is_empty_operator_stack(poper))
  97.         {
  98.             value = calc_data(pdata,poper);
  99.             push_data_stack(pdata,value);
  100.             
  101.         }else{
  102.         
  103.             break;
  104.         }
  105.     }

  106.     value = get_stack_top_data(pdata);

  107.     return value;
  108. }

  109. int special_handing(DataStack *p,OperatorStack *q)
  110. {
  111.     int value;
  112.     char operator;

  113.     while(1)
  114.     {
  115.         operator = get_stack_top_operator(q);

  116.         if(operator == '(')
  117.         {
  118.             pop_operator_stack(q);
  119.             break;
  120.         }
  121.         
  122.         value = calc_data(p,q);
  123.         printf("value = %d\n",value);
  124.         
  125.         push_data_stack(p,value);
  126.         printf("top = %d\n",get_stack_top_data(p));
  127.     }

  128.     return 0;
  129. }

  130. int recive_data(char *p)
  131. {
  132.     int data = 0;
  133.     int i = 0;

  134.     while(1)
  135.     {
  136.         if(!(p[i] >= '0' && p[i] <= '9') || p[i] == '\0')
  137.         {
  138.             break;
  139.         }

  140.         data = data * 10 + p[i] - '0';

  141.         i ++;
  142.     }

  143.     return data;
  144. }

  145. int main()
  146. {
  147.     char buf[MAX];
  148.     int i = 0;
  149.     int value;
  150.     int data = 0;
  151.     int flag = 0;

  152.     DataStack *pdata = (DataStack *)malloc(sizeof(DataStack));
  153.     OperatorStack *poper = (OperatorStack *)malloc(sizeof(OperatorStack));

  154.     //输入数据
  155.     while((buf[i++] = getchar()) != '\n' && i < MAX);
  156.     buf[i-1] = 0;

  157.     //栈初始化
  158.     stack_init(pdata,poper);
  159.     i = 0;
  160.     
  161.     while(buf[i])
  162.     {
  163.         //遇到空格继续下一个字符
  164.         if(buf[i] == ' ')
  165.         {
  166.             i ++;
  167.             continue;
  168.         }

  169.         //收集数据
  170.         if(buf[i] >= '0' && buf[i] <= '9')
  171.         {
  172.             if(flag == 0)
  173.             {
  174.                 data = recive_data(&buf[i]);
  175.                 push_data_stack(pdata,data);
  176.                 printf("data = %d\n",data);
  177.                 flag = 1;
  178.             }
  179.             
  180.         }else{

  181.             //处理()
  182.             if(buf[i] == '(')
  183.             {
  184.                 push_operator_stack(poper,buf[i]);
  185.                 i ++;
  186.                 continue;
  187.             }

  188.             if(buf[i] == ')')
  189.             {
  190.                 special_handing(pdata,poper);
  191.                 i ++;
  192.                 continue;
  193.             }

  194.             //通用处理
  195.             deal_with(pdata,poper,buf[i]);

  196.             flag = 0;
  197.         }

  198.         i ++;
  199.     }

  200.     //最后一次处理,处理同级的运算符
  201.     value = last_deal_with(pdata,poper);

  202.     printf("value = %d\n",value);
  203.         
  204.     return 0;
  205. }
 
阅读(14424) | 评论(2) | 转发(15) |
0

上一篇:约瑟夫问题

下一篇:C语言 C99新增关键字

给主人留下些什么吧!~~

十七岁的回忆2012-04-04 21:48:26

表达式计算~~基础的栈应用

夏冰软件2012-04-01 16:28:52

你的不错,支持一下