白俊1541号です.
https://www.acmicpc.net/problem/1541

質問する

ポテンシャル俊は正数と+,−と括弧で式を構成した.そして勢俊はかっこを全部削除した.
そして勢俊適はかっこをつけて、この式の値を最小限に抑えようとした.
この式の値を最小にするプログラムを適切なかっこで書いてください.

入力

最初の行には数式があります.式は「0」~「9」、「+」、「-」で構成され、最初の文字と最後の文字は数値です.また、2つ以上の演算子が連続して現れず、5桁よりずっと連続した数値はありません.数はゼロから始まることができます.入力式の長さは50以下です.

しゅつりょく

1行目に正解を出力します.

入力例

55-50+40

サンプル出力

-35

考える

問題だけを見るのは難しくないようだが、実施するのは非常に難しい.
約4つのテストケース、3つの内蔵テストケース、

01+0-1

4つのテストケース(計4つ)が問題の解決に役立つと思います.
問題を解いてからGreedyアルゴリズムだと分かったので、他の人のコードを参考にして問題を再開します.

アクション

		String zero = "+";
		// 처음 시작하는 부호가 -가 아닐경우 (양수일 경우)
        // +를 앞에 붙여줌
        
		if( !formula.startsWith("-")) {
			zero += formula;
			formula = zero;
		}

まず、入力されたテストケースをformula変数に保存します.
開始文字列が-でない場合、すなわち、開始文字列が正の値である場合.formula+記号.正数であることを判別するために用いられる.

		int length = formula.length();
		boolean open = false;
		for(int i=0; i<length; i++) {
			char ch = formula.charAt(i);
			
			if(ch == '-' && open == false) {
				open = !open;
				list.add(ch + "(+");
			}
			// + 기호 인데, 괄호가 열려있음을 의미
			else if(ch == '+' && open == true) {
				list.add(String.valueOf(ch));
			}
			else if(ch == '-' && open == true) {
				list.add(")" + ch + "(+");
			}
			else {
				list.add(String.valueOf(ch));
			}
			
			// 마지막줄에 괄호가 열려있을 경우
			if( i == length-1 && open == true) {
				list.add(")");
			}
		}

説明の前に、List<String>を一番上に作成しました.
理由は、式を変更するためですが、変更する式の長さが分からないため、動的な割り当てのためにlistが作成されました.このlistに新しい式が追加されます.
式の長さを繰り返すlength変数を作成します.
ここでは、for文にformula.length()を直接入れることができます.なぜlength変数を作成して書き込まなければならないのか、for文にlength関数を追加すると、
文が繰り返される間、式を使用して値iを比較し続けます.length()が呼び出されます.繰り返し回数が少ない場合はどうでもいいが、大量の繰り返しでは効率が非常に低いため、for文でlength関数を使用することは推奨されない.openは、カッコが現在開いているか閉じているかを判断する変数です.
デフォルトはfalseで、カッコは現在開いていません.chformulaは、if文に単語ごとにカットされ、挿入されます.if(ch == '-' && open == false)-はい、カッコは開いていません.
この場合、符号間の組み合わせが+であるため、「−(+)」はlistに置かれる.
このように-(+40+30)形状の式-開始時に括弧で囲まれます.else if(ch == '+' && open == true)は+ですが、括弧は開いています.
この場合、カッコを閉じずにlistに配置します.かっこの範囲に入り、最小値を作成します.else if(ch == '-' && open == true)-はい、カッコは開いています.
次の-が表示されるので、カッコを閉じてからもう一度カッコを開いて+を付けなければなりません.
つまり、真ん中に-.
たとえば-40+30-20です.この式は-(+40+30)-(+20)になります.
他の場合も、elseはフォーマットを維持するためにlistに配置される.listはString型なので、char型を入れるためにString.valueOf()関数を入力して挿入する必要があります.
最後の行if( i == length-1 && open == true)は、最後の括弧が開いたときに括弧を閉じるための条件文です.

		formula = "";
		for(String str : list) {
			formula += str;
		}

これにより、listの式をformula文字列に再配置することができる.
初期式が55-50+40の場合、変更されたフォーマットは+55-(50+40)です.

これが最後の計算の結果です.

        StringTokenizer st = new StringTokenizer(formula, "-");
        int minus_sum = 0;
        int plus_sum = 0;

        while(st.hasMoreElements()) {
            String temp = st.nextToken();

            if( temp.contains("(")) {
                temp = temp.replace("(", "");
                temp = temp.replace(")", "");

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    minus_sum -= Integer.parseInt(plus_token.nextToken());
                }

            }
            else if ( temp.contains("+")){

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    plus_sum += Integer.parseInt(plus_token.nextToken());
                }

            }
        }

        System.out.println(minus_sum + plus_sum);

負の合計を計算するためのminus_sumを作成します.plus_sum修正された識別子StringTokenizer st = new StringTokenizer(formula, "-");は+30-(+70)-(+20+40)-(+10+100+30)-(+35)
まずすべてをTokenに分ける
重複するタグを保存するformulaは、次のようになります.temp : +30temp : (+70)temp : (+20+40)temp : (+10+100+30)temp : (+35)
のtemp値です.
「(」が付いているすべての値は負であり、「」がない値は正であることがわかります.
したがって、tempcontain関数を確認し、trueの場合は「(」)が存在すると考えます.
重要なのはifクエリの順序も重要であることです.+記号は共有されますが、条件文tempを先に指定する必要があります.「(」は負の値のみです.
負の数の和は、replace関数で「(」と「)」を削除することで計算できます.
次に、残りの+記号をタグ値として指定し、整数に切り捨てて、if( temp.contains("("))plus_tokenをループします.

	StringTokenizer plus_token = new StringTokenizer(temp, "+");
    while(plus_token.hasMoreElements()) {
              minus_sum -= Integer.parseInt(plus_token.nextToken());
    }

次にminus_sum+記号です.
これらの値はいずれも正の値であるため、タグelse if ( temp.contains("+")){として+記号が使用される.
これでそれぞれ負と正和を求めることができます.
結果値は、結果値plus_sumとminus_plusを減算するだけで得られるようになった.
幸いこの問題は考える部分が少なかったー+()この4つの場合、実施は非常に成功しているようです.
もっと違う文字列があると失敗する可能性があるので、他の人のコードを参考にして勉強する必要があります.
正直、これは本当に作成されていないコードですが、私の考え通りに成功して実装できて嬉しいです.

TMI

文字列は本当に簡単なようですが、実現するのは難しいです.
道で知り合いに会ったように、ああ、彼は誰だったっけ...やってるような感じ...

コード#コード#

import java.io.*;
import java.util.*;

public class Main {	

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		List<String> list = new ArrayList<>();
		String formula = br.readLine();
		String zero = "+";

		// 처음 시작하는 부호가 -일 경우 (음수일 경우)
		if( !formula.startsWith("-")) {
			zero += formula;
			formula = zero;
		}


		int length = formula.length();
		boolean open = false;
		for(int i=0; i<length; i++) {
			char ch = formula.charAt(i);

			if(ch == '-' && open == false) {
				open = !open;
				list.add(ch + "(+");
			}
			// + 기호 인데, 괄호가 열려있음을 의미
			else if(ch == '+' && open == true) {
				list.add(String.valueOf(ch));
			}
			else if(ch == '-' && open == true) {
				list.add(")" + ch + "(+");
			}
			else {
				list.add(String.valueOf(ch));
			}

			// 마지막줄에 괄호가 열려있을 경우
			if( i == length-1 && open == true) {
				list.add(")");
			}
		}

		formula = "";
		for(String str : list) {
			formula += str;
		}

        StringTokenizer st = new StringTokenizer(formula, "-");
        int minus_sum = 0;
        int plus_sum = 0;

        while(st.hasMoreElements()) {
            String temp = st.nextToken();

            if( temp.contains("(")) {
                temp = temp.replace("(", "");
                temp = temp.replace(")", "");

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    minus_sum -= Integer.parseInt(plus_token.nextToken());
                }

            }
            else if ( temp.contains("+")){

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    plus_sum += Integer.parseInt(plus_token.nextToken());
                }

            }
        }

        System.out.println(minus_sum + plus_sum);

	} // End of main
} // End of class