日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之棧的應(yīng)用

　　在C++數(shù)據(jù)結(jié)構(gòu)中，棧的應(yīng)用很廣泛，棧的***的用途是解決回溯問(wèn)題，這也包含了消解遞歸；而當(dāng)你用棧解決回溯問(wèn)題成了習(xí)慣的時(shí)候，你就很少想到用遞歸了，比如迷宮求解。另外，人的習(xí)慣也是先入為主的，比如樹(shù)的遍歷，從學(xué)的那天開(kāi)始，就是遞歸算法，雖然書上也教了用棧實(shí)現(xiàn)的方法，但應(yīng)用的時(shí)候，你首先想到的還是遞歸;當(dāng)然了，如果語(yǔ)言本身不支持遞歸(如BASIC)，那棧就是唯一的選擇了——好像現(xiàn)在的高級(jí)語(yǔ)言都是支持遞歸的。

十多年的滕州網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整滕州建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)公司從事“滕州網(wǎng)站設(shè)計(jì)”,“滕州網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

　　如下是表達(dá)式類的定義和實(shí)現(xiàn)，表達(dá)式可以是中綴表示也可以是后綴表示，用頭節(jié)點(diǎn)數(shù)據(jù)域里的type區(qū)分，這里有一點(diǎn)說(shuō)明的是，由于單鏈表的賦值函數(shù)，我原來(lái)寫的時(shí)候沒(méi)有復(fù)制頭節(jié)點(diǎn)的內(nèi)容，所以，要是在兩個(gè)表達(dá)式之間賦值，頭節(jié)點(diǎn)里存的信息就丟了。你可以改寫單鏈表的賦值函數(shù)來(lái)解決這個(gè)隱患，或者你根本不不在兩個(gè)表達(dá)式之間賦值也行。

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

　　幾點(diǎn)說(shuō)明

　　1、表達(dá)式用單鏈表儲(chǔ)存，你可以看到這個(gè)鏈表中既有操作數(shù)又有操作符，如果你看過(guò)我的另一篇文章如何在C++鏈表中鏈入不同類型對(duì)象，這里的方法也是對(duì)那篇文章的補(bǔ)充。

　　2、輸入表達(dá)式時(shí)，會(huì)將原來(lái)的內(nèi)容清空，并且必須按照中綴表示輸入。如果你細(xì)看一下中綴表達(dá)式，你就會(huì)發(fā)現(xiàn)，除了括號(hào)，表達(dá)式的結(jié)構(gòu)是“操作數(shù)”、“操作符”、“操作數(shù)”、……“操作符(=)”，為了統(tǒng)一這個(gè)規(guī)律，同時(shí)也為了使輸入函數(shù)簡(jiǎn)單一點(diǎn)，規(guī)定括號(hào)必須這樣輸入“0(”、“)0”;這樣一來(lái)，“0”就不能作為操作數(shù)出現(xiàn)在表達(dá)式中了。因?yàn)槲覜](méi)有在輸入函數(shù)中增加容錯(cuò)的語(yǔ)句，所以一旦輸錯(cuò)了，那程序就“死”了。

　　3、表達(dá)式求值的過(guò)程是，先變成后綴表示，然后用后綴表示求值。因?yàn)樵瓡v解的是這兩個(gè)算法，并且用這兩個(gè)算法就能完成中綴表達(dá)式的求值，所以我就沒(méi)寫中綴表達(dá)式的直接求值算法。

　　4、Calculate()注釋掉的兩行，“%”是因?yàn)橹粚?duì)整型表達(dá)式合法，“^”的Power()函數(shù)沒(méi)有完成。

　　5、isp()，icp()的返回值，我來(lái)多說(shuō)兩句。‘=’(表達(dá)式開(kāi)始和結(jié)束標(biāo)志)的棧內(nèi)棧外優(yōu)先級(jí)都是最低?！?’棧外最高，棧內(nèi)次最低?！?’棧外次最低，不進(jìn)棧。‘^’棧內(nèi)次最高，棧外比棧內(nèi)低?！痢?’棧內(nèi)比‘^’棧外低，棧外比棧內(nèi)低?！?-’棧內(nèi)比‘×’棧外低，棧外比棧內(nèi)低。這樣，綜合起來(lái)，就有9個(gè)優(yōu)先級(jí)。


文章題目：C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之棧的應(yīng)用
本文地址：http://www.5511xx.com/article/djsjjcd.html