C言語で指定された括弧ペアを使ってバランスの取れた括弧式を出力するプログラム

この記事では、あらかじめ値が定められた4つの変数 a、b、c、d に応じて対応する括弧を出力し、それらをすべて使い切ったバランスの取れた括弧式を生成するCプログラムについて解説します。

問題の概要

各変数は、次の括弧ペアに対応しています。

a … ((
b … ()
c … )(
d … ))

求められているのは、与えられたすべての括弧を使い切ってバランスの取れた括弧式を出力することです。もしバランスの取れた式を構成できない場合は -1 を出力します。答えが複数存在する場合は、そのうちのどれを出力しても構いません。

入出力例

入力: a = 3, b = 2, c = 4, d = 3
出力: (((((()()()()())))))()()

解き方のアプローチ

最初に、与えられた個数の括弧からバランスの取れた式が作れるかどうかを判定します。作成可能な場合は、以下の順序で出力していきます。

• タイプ1の括弧「((」を a 個出力する
• タイプ3の括弧「)(」を c 個出力する
• タイプ4の括弧「))」を d 個出力する
• タイプ2の括弧「()」を b 個出力する

この順序が機能する理由は次のとおりです。「((」はネストの深さを2だけ増やし、「))」は2だけ減らします。途中で深さが負にならず、最後に0へ戻るためには a と d が等しい必要があります。「)(」は深さを変えないため、「((」と「))」の間に自由に配置できます。また「()」はそれ自体で完結したペアなので、どこに出力してもバランスを壊しません。a が 0 の場合は深さを上げる括弧が存在しないため、c と d も 0 であることが条件となります（b だけの構成）。

アルゴリズム

START
ステップ1 -> 関数 void print(int a, int b, int c, int d) を宣言し、int i を用意する
    IF ((a == d && a) || (a == 0 && c == 0 && d == 0))
        i = 1 から i <= a までループして「((」を出力
        i = 1 から i <= c までループして「)(」を出力
        i = 1 から i <= d までループして「))」を出力
        i = 1 から i <= b までループして「()」を出力
    ELSE
        「構成できない」こと（-1）を出力
ステップ2 -> main()
        int a = 3, b = 2, c = 4, d = 3 を宣言
        print(a, b, c, d) を呼び出す
STOP

C言語での実装例

#include<stdio.h>
void print(int a, int b, int c, int d){
    int i;
    if ((a == d && a) || (a == 0 && c == 0 && d == 0)){
        for (i = 1; i <= a; i++)
            printf("((");
        for (i = 1; i <= c; i++)
            printf(")(");
        for (i = 1; i <= d; i++)
            printf("))");
        for (i = 1; i <= b; i++)
            printf("()");
    }
    else
        printf("-1");
}
int main(){
    int a = 3, b = 2, c = 4, d = 3;
    print(a, b, c, d);
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

(((((()()()()())))))()()