首页 > 代码库 > The application of the stack—Parentheses Matching(括号匹配)
The application of the stack—Parentheses Matching(括号匹配)
The thought of the algorithm is as follows:
(1) Initially set up an empty stack, sequentially read in parentheses;
(2) If it is a right parentheses, or it matches the stack top element, or it is illegal;
(3) If it is a left parentheses, it will be pushed into the stack.
When the algorithm is end, if the stack is empty, the parentheses matching is successful;
if the stack is not empty, the parentheses matching is failing.
The codes are as follows(C++):
1 #include "stdafx.h" 2 #include<iostream> 3 #include "string.h" 4 using namespace std; 5 #define stacksize 100 6 //定义栈的结构 7 struct stack{ 8 char stackstr[stacksize]; 9 int top;10 };11 //初始化栈12 void InitStack(stack &s){13 s.top = -1;14 }15 //入栈操作16 void Push(stack &s, char ch){17 if (s.top == stacksize - 1)18 cout << "站已满" << endl;19 else{20 s.top++;21 s.stackstr[s.top] = ch;22 }23 }24 //出栈操作25 char Pop(stack &s){26 if (s.top == -1)27 return 0;28 else{29 char ch = s.stackstr[s.top];30 return ch;31 }32 }33 //判断栈是否为空34 int IsEmpty(stack &s){35 if (s.top == -1)36 return 0;37 else38 return 1;39 }40 //括号匹配41 int PrintMatchedPairs(char *str){42 stack s;43 InitStack(s);44 int strLen = strlen(str);45 for (int i = 0; i < strLen; i++){46 char ch = str[i];47 switch(ch){48 case ‘(‘:49 case ‘[‘:50 case ‘{‘:51 Push(s, ch);52 break;53 case ‘)‘:54 if (Pop(s) != ‘(‘)55 return 0;56 break;57 case ‘]‘:58 if (Pop(s) != ‘[‘)59 return 0;60 break;61 case ‘}‘:62 if (Pop(s) != ‘{‘)63 return 0;64 break;65 }66 }67 int re = 0;68 re = IsEmpty(s);69 if (re == 0)70 return 0;71 if (re == 1)72 return 1;73 }74 int main(){75 char str[100];76 cout << "请输入一个括号的字符串:" << endl;77 cin >> str;78 int re=PrintMatchedPairs(str);79 if (re == 0)80 cout << "括号完全匹配" << endl;81 else82 cout << "括号不匹配"<<endl;83 return 0;84 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。