[BOJ]#2504:かっこの値

質問リンク

質問する

4つの記号「(」、「)」、「[」、「]」を使用して作成されたカッコでは、次のように定義されます.
正しいカッコ列は、1対のカッコの「()」と「[]」のみです.
Xが正しい括弧であれば、「(X)」または「[X]」が正しい括弧になります.
XとYの両方が正しい括弧であれば、それらを結合したXYも正しい括弧になります.
たとえば、「(()[]」または「()」[][[]]」は有効な括弧ですが、「([)]」または「(()()[]」は有効な括弧ではありません.任意の正しい括弧Xについて、その括弧の値(括弧値)を以下のように定義し、値(X)で表します.
かっこ

"()列の値は2です.

かっこ

"[]列の値は3です.

"(X)"のかっこ値は2×値(X)で計算します.

"[X]"のかっこ値は3×値(X)で計算します.

正しい括弧XとYの組み合わせのXYの括弧値は、値(XY)=値(X)+値(Y)から算出される.

たとえば、[[][][][]][]のカッコ値を指定します.()[]'のかっこ値は2+3×3=11なので「()[[]」のかっこ値は2×11=22.「([])」の値は2です.×3=6のため、カッコ全体の値は22+6=28です.
解決すべき問題は、指定したカッコを読み取り、前に定義した方法でカッコ値を計算して出力することです.

入力

最初の行には、カッコを表す文字列(文字列)が表示されます.ただし、長さは1以上、30以下です.

しゅつりょく

最初の行に整数を出力します.カッコ内の値を表します.入力したカッコが無効な場合は、0を出力する必要があります.

入力例1

入力

(()[[]])([])

しゅつりょく

28

入力例2

入力

[][]((])

しゅつりょく

0

📝ろんり

この問題はスタックという資料構造を練習する問題です.以前カッコ検索問題をしたのを覚えていますが、すぐにスタックを使うことを考えることができます.
スタックを作成するときは、学校で勉強しているlinklistを使って実現することができ、いろいろな方法がありますが、c++の標準ライブラリstackを使いました.
stackはLIFO構造のcontainer Adapterです.内部はvector,deque,list conatinerの構造によって実現される.
スタックヘッダファイルを追加すると、スタックジェネレータと関数を使用できます.
基本的には「stack<資料型>変数名」として宣言されます.
stackに提供される関数はpush,pop,top,empty,sizeなどである.

論理的説明

全体的な論理は以下の通りで,中間的に例外処理を行う.

1. 입력 받은 문자열을 하나씩 보면서 닫는 괄호, 여는 괄호, 그 외 문자를 구분한다.

1-1. 닫는 괄호라면,
1-1-1. 해당 괄호와 스택의 top이 올바른 쌍이 될 때까지 pop하며 스택에 있는 값을 더한다.
1-1-2. 올바른 쌍이 됐다면 1-1.에서 계산한값에 해당 쌍에 맞는 값을 곱한 뒤 그 값을 push한다.

1-2. 여는 괄호라면 스택에 push한다. (편의를 위해 '('는 0, '['는 1로 바꿔서 넣는다.)

1-3. 그 외 문자라면 무조건 잘못된 괄호열이라고 판단한다.

2. 입력 받은 문자열을 모두 확인하면 스택에 남아있는 값을 더한다.

コード#コード#

comp()関数に対して0を返す部分は例外処理の部分である.

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;

char paren[31];

int comp()
{
    stack<int> st;
    int temp = 0;
    int result = 0;

    for (int i = 0; i < strlen(paren); i++)
    {
        temp = 0;
        if (paren[i] == ')' || paren[i] == ']')
        {

            while (!st.empty()) {
               
                if ((paren[i] == ')' && st.top() == 0) || (paren[i] == ']' && st.top() == 1)) {
                    st.pop();
                    if (temp == 0) temp = 1;

                    if (paren[i] == ')') temp *= 2;
                    else if (paren[i] == ']') temp *= 3;

                    st.push(temp);
                    break;
                }
                else if ((paren[i] == ')' && st.top() == 1) || (paren[i] == ']' && st.top() == 0)) return 0;
                else {
                    temp += st.top();
                    st.pop();
                }
            }
            if (st.empty()) return 0;
        }
        else if (paren[i] == '(') st.push(0);
        else if (paren[i] == '[') st.push(1); 

        else {
            return 0;
        }
    }
    while (!st.empty()) {
        if (st.top() == 1 || st.top() == 0) {
            return 0;
        }
        result += st.top();
        st.pop();
    }
    return result;
}

int main()
{
    scanf("%s", paren);
    printf("%d", comp());

}

❌コード作成時に発生したエラー❌

スタックにアクセスしたときに空であるかどうかを確認しませんでした.(分割故障原因)
ああ、ああ、この間違いは本当に泣きたい間違いです.😰
この問題を解いたとき、私は本当にたくさん(本当にたくさん、、)採点をして、ほとんど95%がそうでした.
stackにアクセスする場合(すなわちtop()またはpop()))は、stackが空であることを確認する必要があります.
そうでない場合、空のスタックにアクセスして、不正なメモリを参照します.このため、セグメント断層、、、、、
でもこれは終わりじゃない!🤬 (これからは私の最大のシャベルです)
ここまで読んで、아~ 오키~ 그럼 empty 체크하고 top하면 되는거잖아~ if(!st.empty() && st.top()=='(') 뭐 이런식으로 짜면 되겠넹ㅎㅋただし、スタックが空かどうかをチェックする文と残りの比較文をif文にすべて入れることはできません.
すなわち,スタックが空であるか否かをオーバーラップif文で確認し,if文に残りの条件文を書くべきである.if(!st.empty()){ if(st.top()=='(')} こう書きます.
その理由はifゲートを全て打ち込むと!st.empty()がfalse、後に&&演算があるのでifゲートから直接飛び出すかもしれませんが、後のすべての条件が全て確認されて結果が出るのでスタックが空いていることを確認したりスタックに近づいたりするからです.
(書いた後、これは愚かな間違いだと思いましたが、、、、)

例外を注意深く処理しなかった.
多くの問題にも当てはまるが,その問題で述べた内容のみを入力する保証はない.
この問題は()と[]にのみ関連するので,その2つのカッコしか現れないかもしれないが,{}カッコも現れる可能性があるので,この点を考慮して論理を記述する必要がある.
面倒な反例もある.背中が多い.上記のコードを作成する際に見逃す反例は.
([)
())))))
あります.
コードをどのように書くかによって、反例はもちろん違うので、反例が全く思い出せないときは、問題の「問題検索」掲示板を活用しましょう.

整理する

スタック、vector、dequeを書くときに、空であるかどうかを確認し、

にアクセスします.

は、参照エラーを回避するメモリ(例えば、繰り返し文やデータ構造を使用する場合など)

を符号化する.

いたずらなしデバッグ

の例外

をよく考慮する.