一個簡單的程式，展示了連結串列如何作為棧使用，具有
後進先出（LIFO）的訪問方式。
本程式基於
iterator函式。程式將提示使用者輸入一個字串。該函式將該字串作為引數。然後，函式將解析整個字串。每次迭代都會進行三個檢查。
1. 如果括號不匹配，例如'{'與']'匹配
2. 如果只有開括號
3. 如果只有閉括號
過程流程是程式逐個字元讀取字串輸入。如果當前迭代的字元是開括號，即'{'、'['或'('，它將被推入棧物件
list。現在，如果程式遇到閉括號，它將呼叫
list的pop函式，並檢查彈出的物件。如果彈出的物件是'\a'，它是一個標誌，表示棧為空。這意味著字串包含一個沒有配對的閉括號。這是一個不一致，所以它將返回false。否則，將比較彈出的物件和當前迭代的字元以檢查它們是否匹配。如果匹配，迴圈將繼續，否則將返回false。在程式解析完整個字串後，它將檢查棧是否為空。此時，如果棧不為空，則意味著存在某個開括號沒有對應的閉括號。所以這將返回false。最後，如果上述三個檢查都成功，函式將返回true。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include <iostream>
#include <string>
#include <Windows.h>
struct node
{
char c;
node* next;
node()
{
next = nullptr;
}
};
class stack
{
private:
node* head;
public:
stack()
: head(nullptr)
{}
bool is_empty()
{
if(!this->head)
return true;
else
return false;
}
void push(char c)
{
node* p = new node;
p->c = c;
if(this->is_empty())
this->head = p;
else
{
p->next = this->head;
this->head = p;
}
}
char pop()
{
if(this->is_empty())
return '\a';
else
{
node* tmp = this->head;
this->head = this->head->next;
char c = tmp->c;
delete tmp;
return c;
}
}
};
//////////////////////////////////////////////////////////////////////////
inline bool iterator(std :: string& exp)
{
stack list;
for(int i=0;i<exp.size();i++)
{
if(exp[i] == '[' ||
exp[i] == '{' ||
exp[i] == '(')
list.push(exp[i]);//when an opening bracket is found, push it in the stack
if (exp[i] == ']' ||
exp[i] == '}' ||
exp[i] == ')')
{
char c = list.pop();
if (c == '\a')
return false; //if the expression has only closing brackets
else
{
if(c == '[' && exp[i] == ']' ||
c == '{' && exp[i] == '}' ||
c == '(' && exp[i] == ')');
else
return false; //if mismatch
}
}
}
if (!list.is_empty())
return false; //if the expression has only opening brackets
else
return true;
}
int main()
{
SetConsoleTitle("PARANTHESIS CHECKER");
std :: string exp;
std :: cout<<"Enter the expression: ";
getline(std :: cin,
exp);
if(iterator(exp))
std :: cout<<"The expression "<<exp<<" is consistent in brackets.\n\n";
else
std :: cout<<"The expression "<<exp<<" is inconsistent in brackets.\n\n";
system("pause");
return 0;
}
|
輸出
Enter the expression: 3x+432[
The expression 3x+432[ is inconsistent in brackets.
|
Enter the expression: 3x+(4/7+[6/a])
The expression 3x+(4/7+[6/a]) is consistent in brackets.
|
