文章

14

粉丝

230

获赞

26

访问

71.2k

头像
两次来回遍历解决括号匹配问题
P1296 北京大学机试题
发布于2022年8月5日 15:02
阅读数 5.1k

算法思路:两次来回遍历输入

第一次遍历输入字符串(从左往右,标记空格和?)

  •  如果是左括号,入栈,同时标记数组的相应位置置空格
  •  如果是右括号,则判断是否为栈顶元素是否匹配,匹配,标记数组的相应位置置空格,不匹配,标记数组的相应位置置‘?
  •  如果是其它字符,标记数组的相应位置置空格

第二次遍历输入字符串(从右往左,标记$)

  •  如果是右括号,入栈
  •  如果是左括号,则判断是否为栈顶元素是否匹配,不匹配,标记数组的相应位置置‘$’

带注释代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string str;
    stack<char> s;

    while(cin>>str)
    {
        char aa[100];
        int len  = str.size();
        for(int i=0; i<len; i++)
        {
            if(str[i]=='(') //左括号入栈,标记数组记为' '
            {
                s.push('(');
                aa[i]=' ';
            }
            else if(str[i]==')')//右括号判断是否与栈顶元素匹配
            {
                if(!s.empty()&&s.top()=='(') //匹配,则出栈,标记数组记为' '
                {
                    s.pop();
                    aa[i]=' ';
                }
                else  aa[i]='?'; //否则,右括号不匹配,标记数组记为'?'

            }
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发