首页 > 代码库 > 栈应用之括号匹配
栈应用之括号匹配
栈的使用之括号匹配
Char s[n]是一个字符串数组。Stack是一栈，i是元素对应的下表。设一个char flag[n]数组，用来标记是否匹配，数组中数值是‘l’（左不匹配，即没有找到右括号），‘r’（右不匹配），‘o’匹配成功。
算法描述：
（1）遍历该字符串数组。
While（遍历）{
if遇到‘（’，do stack.push(i)(i 是‘（’对应的数组下表)，flag[i]=’o’（不一定就是匹配成功，以后遍历完如果stack还有元素，说明没有左匹配，要改成‘l’；如果没有，则就是真正的匹配成功了）；
if遇到‘）’，if stack不为空，do stack.pop()（说明匹配），flag[i]=’o’。）；如果为空就不匹配，flag[i]=’r’
} do (2)
(2)如果stack.empty是false，则do while（!stack.empty()）{ flag[stack.top()]=’r’（将之前的‘o’修改掉）；stack.pop() }
1 // try.cpp : Defines the entry point for the console application. 2 // 3 /************************************************************************/ 4 /* 栈应用之括号匹配 */ 5 /************************************************************************/ 6 #include "stdafx.h" 7 #include"stack" 8 #include"string.h" 9 using namespace std;10 #define FOR(n) for (int i=0;i<n;i++)11 stack<int> mystack;12 char flag[1000];13 char str[1000];14 int main(){15 16 while (scanf("%s",str)!=EOF)17 {18 19 memset(flag,0,strlen(str));20 FOR(strlen(str)){21 if (str[i]==‘(‘)22 {23 mystack.push(i);24 flag[i]=‘o‘;25 }26 else if(str[i]==‘)‘){27 if (!mystack.empty())28 {29 mystack.pop();30 flag[i]=‘o‘;31 }32 else flag[i]=‘r‘;33 }34 }35 while (!mystack.empty())36 {37 flag[mystack.top()]=‘l‘;38 mystack.pop();39 }40 flag[i]=‘0‘;41 puts(str);42 puts(flag);43 44 }45 }
栈应用之括号匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。