棧的應用

• 括號匹配問題：
• • 原理：
  • 代碼實現：

括號匹配問題：

原理：

1、括號匹配成功的情況：棧為空
2、括號匹配失敗的情況：
　　a、下一個為右括號但是和棧頂左括號不匹配
　　ｂ、下一個是右括號但棧以空

　　ｃ、所有的空號都匹配完成后棧不空
　　

代碼實現：

1、方法一

bool isValid(char * s){char *stack = (char*)malloc(strlen(s)+1);int top = 0;int i;// if(s[0] == ')' || s[0] == ']' || s[0] == '}')// return false;for(i = 0;i < strlen(s);i ++){if(s[i] == '(' || s[i] == '[' || s[i] == '{'){top ++;stack[top] = s[i];}else {if((s[i] == ')' && stack[top] == '(') || (s[i] == ']' && stack[top] == '[') || (s[i] == '}' && stack[top] == '{'))top --;elsereturn false;}}if(top == 0)return true;elsereturn false; }

方法二：

bool isValid(char * s){char *stack = (char*)malloc(strlen(s)+1);int top = 0;int i;// if(s[0] == ')' || s[0] == ']' || s[0] == '}')// return false;for(i = 0;i < strlen(s);i ++){if(s[i] == '(' || s[i] == '[' || s[i] == '{'){top ++;stack[top] = s[i];}else //由ASCALL表可知if((stack[top]+1) == s[i] || (stack[top]+2) == s[i])top --;elsereturn false;}}if(top == 0)return true;elsereturn false; }

方法三：

bool isValid(char *s){//SqStack S;char *Stack = (char*)malloc(strlen(s));//InitStack(S);int top = -1;for(int i = 0;i < strlen(s);i ++){if(s[i] == '(' || s[i] == '[' || s[i] == '{'){top ++;Stack[top] = s[i];}else{if(top == -1)return false;char topElem;if(s[i] == ')' && Stack[top] != '(')return false;if(s[i] == ']' && Stack[top] != '[')return false;if(s[i] == '}' && Stack[top] != '{')return false;top --;} }if(top == -1)return true;elsereturn false; }

總結

以上是生活随笔為你收集整理的数据结构之栈的应用：括号匹配问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。