[伯俊]9012かっこ

質問する

括弧文字列(Parentosis String,PS)は、2つの括弧記号「(」と「)」からなる文字列である.ここで、括弧形状が正しい文字列を正しい括弧文字列(Valid PS,VPS)と呼ぶ.括弧の「()」文字列をデフォルトVPSと呼びます.xがVPSであれば、括弧に入れる新しい文字列「(x)」もVPSとなります.また,2つのVPSxとyを接続した新しい文字列xyもVPSとなる.例えば、「()()()」「((())」はVPSであるが、「()(」()、「()()())」と「(((()」はVPSではなく文字列である.
入力した括弧文字列がVPSであるかどうかを判断し、結果をYESとNOとして表す必要があります.

にゅうしゅつりょく

Input
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
Output
NO
NO
YES
NO
YES
NO

に答える

この問題はスタックで解決できる.VPSの特性を考えると、

のカッコを1回開くには、閉じなければなりません.( '(' )

閉じた括弧は、開いた括弧より先に開くことはできません.

すべての括弧にはペアが必要です.

スタックに両方を適用すると、次の問題を解決できます.

オープンカッコが表示された場合は、スタックにPUSHを設定します.
2-1. 閉じたカッコが開いたカッコより先にある場合、VPSは満たされません.
2-2. 2-1でなければスタックでPOPを再生します.

すべてのプロセスが終了すると、スタックは空になる必要があります.

以上の過程で問題を解決した.

コード#コード#

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

bool checkVPS(char *command){
    stack<char> parenthesis;


    for(int i = 0; i < strlen(command); i++){
        if(command[i] == ')'){
            if(parenthesis.empty()) {
                return false;
            }
            else parenthesis.pop();
        }
        else{
            parenthesis.push(command[i]);
        }
    }   

    return parenthesis.empty();
}

int main(){
    int numberOfCommand = -1;
    cin >> numberOfCommand;
    char commandLine[51];
    char *command = commandLine;

    for(int i = 0; i < numberOfCommand; i++){
        cin >> command;
        if(checkVPS(command)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

ポスト

最初は「ランタイムエラー」(NeverBenull)を受け取っていましたが、入力したコマンド文字列のポインタにサイズが割り当てられていなかったことによるエラーだと思いました.

コマンドを受信した文字列の長さに問題があるというエラーメッセージが表示されます.問題では、括弧の文の長さは2<=length<=50であり、50個の括弧を入力すると文字列の末尾に0を入力できないため、エラーの文が常に受信されます.入力文字列の長さを51に変更すると、正解が得られます.

最初はStackタイプがintで、intタイプが4 Byte、charタイプが1 B yteと考えられていたので、メモリ使用率の観点からcharタイプを使うのは効率的でした.

解答と後期のほかに、他のアルゴリズムやコードの不要な部分、またはより有効な部分があることを教えてください。