YoungXie 2012-10-13 18:23 发表评论

 1 /*
 2 输入一个表达式，如果有表达式中有括号，判断该括号是否匹配
 3 
 4 
 5 */
 6 #include <iostream>
 7 using namespace std;
 8 
 9 
10 typedef unsigned int UINT;
11 typedef char CHAR;
12 typedef unsigned char UICHAR;
13 
14 #define LEFTCIRCLEBRACKET    '('
15 #define RIGHTCIRCLEBRACKET    ')'
16 #define LEFTSQUABRACKET      '['
17 #define RIGHTSQUABRACKET      ']'
18 
19 
20 //栈的元素
21 typedef struct stacknode
22 {
23     CHAR chstackData;
24     struct stacknode* pnext;
25 }STACKNODE;
26 
27 
28 //定义一个栈类
29 class cBracketMatchStack
30 {
31     public:
32         cBracketMatchStack();
33         ~cBracketMatchStack();
34         bool Init(CHAR* cTmpPre, UINT uiTmpLength);
35         void close();
36         void processMatch();
37         bool pushStackNode(CHAR chstacknodeValue);//入栈
38         bool popStackNode();//出栈
39         void createNode();
40     private:
41         //UINT m_uiStackLength;//栈的长度
42         STACKNODE* m_sntop;//永远指向栈顶元素，当为空时为NULL
43         CHAR* m_pStrPre;
44         bool m_bFirstisWrong;
45 };
46 
47 

  1 
  2 
  3 #include "cBracketMatchStack.h"
  4 
  5 cBracketMatchStack::cBracketMatchStack()
  6 {
  7     m_sntop = NULL;
  8     m_pStrPre = NULL;
  9     m_bFirstisWrong = false;
 10 }
 11 cBracketMatchStack::~cBracketMatchStack()
 12 {
 13     close();
 14 }
 15 void cBracketMatchStack::close()
 16 {
 17     while (NULL != m_sntop)
 18     {
 19         STACKNODE* sTmpNode = m_sntop->pnext;
 20         delete m_sntop;
 21         m_sntop = NULL;
 22         m_sntop = sTmpNode;
 23     }
 24     if (NULL != m_pStrPre)
 25     {
 26         delete []m_pStrPre;
 27         m_pStrPre = NULL;
 28     } 
 29 }
 30 //输入一个表达式，和该表达式的长度
 31 bool cBracketMatchStack::Init(CHAR* cTmpPre, UINT uiTmpLength)
 32 {
 33     m_sntop = NULL;
 34     m_pStrPre = new char[uiTmpLength+1];
 35     if (NULL == m_pStrPre)
 36     {
 37         cout<<"malloc memory is failured."<<endl;
 38         return false;
 39     }
 40     //拷贝需要匹配表达式的输入字符串
 41     strncpy(m_pStrPre, cTmpPre, uiTmpLength);
 42     m_pStrPre[uiTmpLength] = '\0';
 43     //cout<<"the input character is:"<<m_pStrPre<<endl;
 44     
 45     return true;
 46 }
 47 //开始处理匹配过程
 48 void cBracketMatchStack::processMatch()
 49 {
 50     CHAR* cTmp = m_pStrPre;
 51 
 52     while ((NULL != cTmp) && ('\0' != *cTmp))
 53     {
 54         //char ccTmp = *cTmp;
 55         if ((LEFTCIRCLEBRACKET == *cTmp) || (RIGHTCIRCLEBRACKET == *cTmp) 
 56             || (LEFTSQUABRACKET == *cTmp) || (RIGHTSQUABRACKET == *cTmp))
 57         {
 58             pushStackNode(*cTmp);
 59         }
 60         //指向下一个字符
 61         ++cTmp;
 62     }
 63     //走到这就表示整个表达式已经入栈完毕了，并且在入栈的过程中也已经进行了表达式的匹配工作
 64     //表达式的匹配的最终结果是该栈是为空栈，否则该表达式为不匹配
 65     if ((NULL == m_sntop) && (false == m_bFirstisWrong))
 66     {
 67         cout<<"This expression is valid."<<endl;
 68     }
 69     else
 70     {
 71         cout<<"This expression is not valid."<<endl;
 72     }
 73     close();
 74 }
 75 void cBracketMatchStack::createNode()
 76 {
 77     STACKNODE* pTmpNode = NULL;
 78     pTmpNode = new STACKNODE;
 79     if (NULL == pTmpNode)
 80     {
 81         cout<<"malloc memory is failured."<<endl;
 82         exit(-1);
 83     }
 84     else
 85     {
 86         //非空栈
 87         if (NULL != m_sntop)
 88         {
 89             pTmpNode->pnext = m_sntop;
 90             m_sntop = pTmpNode;
 91         }
 92         else
 93         {
 94             //空栈
 95             m_sntop = pTmpNode;
 96             m_sntop->pnext = NULL;
 97         }
 98         
 99     }    
100 }
101 //元素入栈
102 bool cBracketMatchStack::pushStackNode(CHAR chstacknodeValue)
103 {
104     //bool bTmpPushRst = false;
105 
106     if (NULL == m_sntop)
107     {
108         //首次进入的就是']'或')'，直接返回错误
109         if ((RIGHTCIRCLEBRACKET == chstacknodeValue) || (RIGHTSQUABRACKET == chstacknodeValue))
110         {
111             m_bFirstisWrong = true;
112             return false;
113         }
114         createNode();
115         m_sntop->chstackData = chstacknodeValue;
116     }
117     else
118     {
119         //输入的是')'，但是当前栈顶存储的不是'('，则该表达式不匹配。
120         if ((RIGHTCIRCLEBRACKET == chstacknodeValue) && (LEFTCIRCLEBRACKET != m_sntop->chstackData))
121         {
122             return false;
123         }
124         else if ((RIGHTCIRCLEBRACKET == chstacknodeValue) && (LEFTCIRCLEBRACKET == m_sntop->chstackData))
125         {
126             //匹配成功，POP栈顶元素
127             popStackNode();
128             
129         }
130         //输入的是']',但是当前栈顶存储的不是'['，则该表达式不匹配
131         else if ((RIGHTSQUABRACKET== chstacknodeValue) && (LEFTSQUABRACKET != m_sntop->chstackData))
132         {
133             return false;
134         }
135         else if ((RIGHTSQUABRACKET== chstacknodeValue) && (LEFTSQUABRACKET == m_sntop->chstackData))
136         {
137             //匹配成功，POP栈顶元素
138             popStackNode();
139         }
140         else
141         {
142             //剩下的就是'('或'['
143             createNode();
144             m_sntop->chstackData = chstacknodeValue; 
145         }
146     }
147 }
148 
149 //出栈
150 bool cBracketMatchStack::popStackNode()
151 {
152     bool bTmpPopRst = false;
153     
154     if (NULL != m_sntop)
155     {
156         STACKNODE* pTmpNode = m_sntop->pnext;
157         delete m_sntop;
158         m_sntop = pTmpNode;
159         bTmpPopRst = true;
160     }
161     else
162     {
163         cout<<endl;
164         cout<<"there is no element in this stack."<<endl;
165     }
166 
167     return bTmpPopRst;
168 }
169 

YoungXie 2012-04-17 22:15 发表评论