头文件：
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