美文网首页
爱奇艺-笔试刷题2018-07-17

爱奇艺-笔试刷题2018-07-17

作者: Dodo159753 | 来源:发表于2018-07-17 07:54 被阅读0次

    题目描述:

    /**
    一个完整的括号字符串定义规则如下:
    1、空字符串是完整的。
    2、如果s是完整的字符串,那么(s)也是完整的。
    3、如果s和t是完整的字符串,将它们连接起来形成的st也是完整的。
    例如,"(()())", ""和"(())()"是完整的括号字符串,"())(", "()(" 和 ")"是不完整的括号字符串。
    牛牛有一个括号字符串s,
    现在需要在其中任意位置尽量少地添加括号,
    将其转化为一个完整的括号字符串。
    请问牛牛至少需要添加多少个括号。
    输入描述:
    输入包括一行,一个括号序列s,序列长度length(1 ≤ length ≤ 50).
    s中每个字符都是左括号或者右括号,即'('或者')'.
    输出描述:
    输出一个整数,表示最少需要添加的括号数
    输入例子1:
    (()(()
    输出例子1:
    2
    */
    
    

    思路如下:

    其实就是找判断合法性的过程中剩下多少个'(' 或者缺多少个'('
    这里不需要用真正的栈只需一个指针维护模拟栈的大小即可
    还有没法匹配的')'数目即可

    代码如下:

    #include<stdio.h>
    #include<iostream>
     
    using namespace std;
     
    int main()
    {
        string line;
        cin>>line;
        int stackSize=0, moreRightBracketNum=0;//多余的)括号
        for(int i=0; line[i]!='\0'; i++){
            if(line[i]!='(' && line[i]!=')')
                return -1;
            if(line[i]=='(')
                stackSize++;
            else if(line[i]==')'){
                if(stackSize>0)
                    stackSize--;
                else
                    moreRightBracketNum++;
            }
        }
        printf("%d", stackSize+moreRightBracketNum);
        return 0;
    }
     
     
    
    

    相关文章

      网友评论

          本文标题:爱奇艺-笔试刷题2018-07-17

          本文链接:https://www.haomeiwen.com/subject/rgzipftx.html