1、基于栈的应用
括号匹配算法是栈的一个典型应用;所以的借用栈来实现,保存相应的信息;
算法思想:遇到第一个字符, 判断栈空,字符入栈,其后的字符和栈顶元素进行比较,括号匹配的话,则栈顶元素出栈,否则,当前元素入栈,直到遇到 0 结束标志;最后根据栈空判断,空:括号匹配,否则,不匹配;
例:([{}]) 是匹配的括号,为正确的;
2、代码实现
- #include<iostream>
- #include<stack>
- using namespace std;
- typedef unsigned char boolean;
- #define TRUE 1
- #define FALSE 0
- boolean backetMatch(char *str);
- boolean backetMatch(char *str){
- stack<int> s;
- int i = 0;
- while(str[i]){
- if(s.empty()){
- s.push(str[i]);
- }else{
- if(s.top() == ')' || s.top() == ']' || s.top() == '}'){
- return FALSE; //首先出现右括号的,肯定是不匹配的;
- }
- if(s.top() == '('){ //为'('的情况
- if(str[i] == ')'){
- s.pop();
- }else{
- s.push(str[i]);
- }
- }else if(s.top() == '['){ //为'['的情况
- if(str[i] == ']'){
- s.pop();
- }else{
- s.push(str[i]);
- }
- }else if(s.top() == '{'){ //为'{'的情况
- if(str[i] == '}'){
- s.pop();
- }else{
- s.push(str[i]);
- }
- }
- }
- i++;
- }
- if(s.empty()){
- return TRUE;
- }else{
- return FALSE;
- }
- }
- int main(void){
- char *str = "({[])}";
- boolean flag;
- flag = backetMatch(str);
- if(flag){
- printf("括号匹配\n");
- }else{
- printf("括号不匹配\n");
- }
- return 0;
- }
3、结果截图
来源: http://www.bubuko.com/infodetail-1962711.html