信息学奥赛一本通 1355：字符串匹配问题(strs)

【题目链接】

ybt 1355：字符串匹配问题(strs)

【题目考点】

1. 栈

【解题思路】

设数组pri，pri[括号字符]是个整数表示括号的优先级。优先级从低到高为：<([{，左括号优先级为正数，右括号优先级为负数。
这里设pri[右括号] = -pri[左括号]，同类的左右括号的优先级数值是相反数的关系，这样就可以用pri来判断两个括号是否配对。
遍历整个字符串

• 如果遇到左括号：
  • 如果栈空，则入栈。
  • 如果栈不空
    • 如果当前左括号优先级小于等于栈顶左括号优先级，左括号入栈。
    • 否则不匹配。
• 如果遇到右括号
  • 如果栈空，则不匹配。
  • 如果栈不空
    • 看栈顶左括号能否与该右括号配对，如果配对则出栈
    • 否则不匹配。

结束遍历字符串后，看栈是否为空

• 如果栈空，则匹配。
• 如果栈不空，则不匹配。

以上为基本写法，为“写法1”。也可以根据以上逻辑将入栈、出栈的条件做整合，减少if嵌套的层数，得到“写法2”。

至于多组数据问题，可以将对一组数据的求解写在函数里，每次求解时调用函数。也可以都写在主函数里，这样写时要注意在每次求解前设置相关变量的初始值。

【题解代码】

写法1：if嵌套 分别判断，将对一组数据的求解写在函数中

#include
using namespace std;
int pri[128];//pri[i]:字符i的优先级
void initPri()//初始化括号的优先级
{//左括号都是正数，右括号都是负数，配对的括号的优先级互为相反数 pri['<'] = 1;pri['('] = 2;pri['['] = 3;pri['{'] = 4; pri['>'] = -1;pri[')'] = -2;pri[']'] = -3;pri['}'] = -4;
}
void solve()//求解一组数据 
{stack<char> stk;string s;cin >> s;for(int i = 0; i < s.length(); ++i){if(pri[s[i]] > 0)//如果s[i]是左括号 {if(stk.empty())stk.push(s[i]);else {if(pri[s[i]] <= pri[stk.top()])stk.push(s[i]);else{cout << "NO" << endl;return;}}}else//如果s[i]是右括号 {if(stk.empty()){cout << "NO" << endl;return;}else{if(pri[s[i]] + pri[stk.top()] == 0)stk.pop();else{cout << "NO" << endl;return;}}}}if(stk.empty())cout << "YES" << endl;elsecout << "NO" << endl;
}
int main()
{initPri();int n;cin >> n;while(n--)solve();return 0;
}

写法2：整合判断条件，在主函数中处理多组数据

#include
using namespace std;
int pri[128];//pri[i]:字符i的优先级
void initPri()
{pri['<'] = 1;pri['('] = 2;pri['['] = 3;pri['{'] = 4;pri['>'] = -1;pri[')'] = -2;pri[']'] = -3;pri['}'] = -4;
}
int main()
{initPri();stack<char> stk;string s;int n;bool isOver;cin >> n;while(n--){stk = stack<char>();//清空栈 cin >> s;isOver = false;for(int i = 0; i < s.length(); ++i){if(pri[s[i]] > 0 && (stk.empty() || pri[s[i]] <= pri[stk.top()]))//入栈条件 stk.push(s[i]);else if(pri[s[i]] < 0 && !stk.empty() && pri[s[i]] + pri[stk.top()] == 0)//出栈条件 stk.pop();else//不匹配条件 {isOver = true;break; }}if(!isOver && stk.empty())cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！