C++数据结构学习之栈的应用

  在C++数据结构中,的应用很广泛,栈的***的用途是解决回溯问题,这也包含了消解递归;而当你用栈解决回溯问题成了习惯的时候,你就很少想到用递归了,比如迷宫求解。另外,人的习惯也是先入为主的,比如树的遍历,从学的那天开始,就是递归算法,虽然书上也教了用栈实现的方法,但应用的时候,你首先想到的还是递归;当然了,如果语言本身不支持递归(如BASIC),那栈就是唯一的选择了——好像现在的高级语言都是支持递归的。

十多年的滕州网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都全网营销的优势是能够根据用户设备显示端的尺寸不同,自动调整滕州建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联公司从事“滕州网站设计”,“滕州网站推广”以来,每个客户项目都认真落实执行。

  如下是表达式类的定义和实现,表达式可以是中缀表示也可以是后缀表示,用头节点数据域里的type区分,这里有一点说明的是,由于单链表的赋值函数,我原来写的时候没有复制头节点的内容,所以,要是在两个表达式之间赋值,头节点里存的信息就丢了。你可以改写单链表的赋值函数来解决这个隐患,或者你根本不不在两个表达式之间赋值也行。

 
 
 
  1. #ifndef Expression_H  
  2. #define Expression_H  
  3. #include "List.h"  
  4. #include "Stack.h"  
  5. #define INFIX 0  
  6. #define POSTFIX 1  
  7. #define OPND 4  
  8. #define OPTR 8  
  9.  
  10. template  class ExpNode  
  11. {  
  12.  public:  
  13.   int type;  
  14.   union { Type opnd; char optr;};  
  15.   ExpNode() : type(INFIX), optr('=') {}  
  16.   ExpNode(Type opnd) : type(OPND), opnd(opnd) {}  
  17.   ExpNode(char optr) : type(OPTR), optr(optr) {}  
  18. };  
  19.  
  20. template  class Expression : List  >  
  21. {  
  22.  public:  
  23.   void Input()  
  24.   {  
  25.    MakeEmpty(); Get()->type =INFIX;  
  26.    cout << endl << "输入表达式,以=结束输入" << endl;  
  27.    Type opnd; char optr = ' ';  
  28.    while (optr != '=')  
  29.    {  
  30.     cin >> opnd;   
  31.     if (opnd != 0)  
  32.     {  
  33.      ExpNode  newopnd(opnd);  
  34.      LastInsert(newopnd);  
  35.     }  
  36.     cin >> optr;  
  37.     ExpNode  newoptr(optr);  
  38.     LastInsert(newoptr);  
  39.    }  
  40.   }  
  41.   void Print()  
  42.   {  
  43.    First();  
  44.    cout << endl;  
  45.    for (ExpNode  *p = Next(); p != NULL; p = Next() )  
  46.    {  
  47.     switch (p->type)  
  48.     {  
  49.      case OPND:  
  50.       cout << p->opnd; break;  
  51.      case OPTR:  
  52.       cout << p->optr; break;  
  53.      default: break;  
  54.     }  
  55.     cout << ' ';  
  56.    }  
  57.    cout << endl;  
  58.   }  
  59.   Expression & Postfix() //将中缀表达式转变为后缀表达式  
  60.   {  
  61.    First();  
  62.    if (Get()->type == POSTFIX) return *this;  
  63.    Stack s; s.Push('=');  
  64.    Expression temp;  
  65.    ExpNode  *p = Next();  
  66.    while (p != NULL)  
  67.    {  
  68.     switch (p->type)  
  69.     {  
  70.      case OPND:  
  71.        temp.LastInsert(*p); p = Next(); break;  
  72.      case OPTR:  
  73.        while (isp(s.GetTop()) > icp(p->optr) )  
  74.        {  
  75.         ExpNode  newoptr(s.Pop());  
  76.         temp.LastInsert(newoptr);  
  77.        }  
  78.        if (isp(s.GetTop()) == icp(p->optr) )  
  79.        {  
  80.         s.Pop(); p =Next(); break;  
  81.        }  
  82.        s.Push(p->optr); p = Next(); break;  
  83.      default: break;  
  84.     }  
  85.    }  
  86.    *this = temp;  
  87.    pGetFirst()->data.type = POSTFIX;  
  88.    return *this;  
  89.   }  
  90.  
  91.   Type Calculate()  
  92.   {  
  93.    Expression temp = *this;  
  94.    if (pGetFirst()->data.type != POSTFIX) temp.Postfix();  
  95.    Stack  s; Type left, right;  
  96.    for (ExpNode  *p = temp.Next(); p != NULL; p = temp.Next())  
  97.    {  
  98.     switch (p->type)  
  99.     {  
  100.      case OPND:  
  101.       s.Push(p->opnd); break;  
  102.      case OPTR:  
  103.       right = s.Pop(); left = s.Pop();  
  104.       switch (p->optr)  
  105.       {  
  106.      case '+': s.Push(left + right); break;  
  107.      case '-': s.Push(left - right); break;  
  108.      case '*': s.Push(left * right); break;  
  109.      case '/': if (right != 0) s.Push(left/right); else return 0; break;  
  110.       // case '%': if (right != 0) s.Push(left%right); else return 0; break;  
  111.       // case '^': s.Push(Power(left, right)); break;  
  112.      default: break;  
  113.     }  
  114.     default: break;  
  115.    }  
  116.   }  
  117.   return s.Pop();  
  118. }  
  119.  
  120. private:  
  121.  int isp(char optr)  
  122.  {  
  123.   switch (optr)  
  124.   {  
  125.    case '=': return 0;  
  126.    case '(': return 1;  
  127.    case '^': return 7;  
  128.    case '*': return 5;  
  129.    case '/': return 5;  
  130.    case '%': return 5;  
  131.    case '+': return 3;  
  132.    case '-': return 3;  
  133.    case ')': return 8;  
  134.    default: return 0;  
  135.   }  
  136.  }  
  137.  
  138.  int icp(char optr)  
  139.  {  
  140.   switch (optr)  
  141.   {  
  142.    case '=': return 0;  
  143.    case '(': return 8;  
  144.    case '^': return 6;  
  145.    case '*': return 4;  
  146.    case '/': return 4;  
  147.    case '%': return 4;  
  148.    case '+': return 2;  
  149.    case '-': return 2;  
  150.    case ')': return 1;  
  151.    default: return 0;  
  152.   }  
  153.  }  
  154. };  
  155.  
  156. #endif 

  几点说明

  1、表达式用单链表储存,你可以看到这个链表中既有操作数又有操作符,如果你看过我的另一篇文章如何在C++链表中链入不同类型对象,这里的方法也是对那篇文章的补充。

  2、输入表达式时,会将原来的内容清空,并且必须按照中缀表示输入。如果你细看一下中缀表达式,你就会发现,除了括号,表达式的结构是“操作数”、“操作符”、“操作数”、……“操作符(=)”,为了统一这个规律,同时也为了使输入函数简单一点,规定括号必须这样输入“0(”、“)0”;这样一来,“0”就不能作为操作数出现在表达式中了。因为我没有在输入函数中增加容错的语句,所以一旦输错了,那程序就“死”了。

  3、表达式求值的过程是,先变成后缀表示,然后用后缀表示求值。因为原书讲解的是这两个算法,并且用这两个算法就能完成中缀表达式的求值,所以我就没写中缀表达式的直接求值算法。

  4、Calculate()注释掉的两行,“%”是因为只对整型表达式合法,“^”的Power()函数没有完成。

  5、isp(),icp()的返回值,我来多说两句。‘=’(表达式开始和结束标志)的栈内栈外优先级都是最低。‘(’栈外最高,栈内次最低。‘)’栈外次最低,不进栈。‘^’栈内次最高,栈外比栈内低。‘×÷%’栈内比‘^’栈外低,栈外比栈内低。‘+-’栈内比‘×’栈外低,栈外比栈内低。这样,综合起来,就有9个优先级。

标题名称:C++数据结构学习之栈的应用
链接分享:http://www.gawzjz.com/qtweb/news27/179827.html

网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联