Codeforces Round #308 Div2 E: Vanya and Brackets

問題

codeforces.com

解法

しゃくとり法。

コード

import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		sc.close();
		int N = input.length();
		if (N == 1) {
			System.out.println(input);
			return;
		}

		long max = calculate(input);
		for (int i = 0; i < N; i += 2) {
			// +が連続している時はスキップ
			if (i > 0 && input.charAt(i - 1) == '+' && (i == 2 || input.charAt(i - 3) == '+')) {
				continue;
			}
			for (int j = i + 2; j < N; j += 2) {
				if (j < N - 1 && input.charAt(j + 1) == '+' && (j == N - 3 || input.charAt(j + 3) == '+')) {
					// +が連続している時はスキップ
					continue;
				}

				String newS = "";
				if (i > 0) {
					newS += input.substring(0, i);
				}
				long m = calculate(input.substring(i, j + 1));
				newS += String.valueOf(m);
				if (j + 1 < N) {
					newS += input.substring(j + 1, N);
				}
				max = Math.max(max, calculate(newS));
			}
		}
		System.out.println(max);
	}

	private long calculate(String string) {
		String[] sp = string.split("\\+");
		for (int i = 0; i < sp.length; i++) {
			if (sp[i].indexOf("*") != -1) {
				String[] mul = sp[i].split("\\*");
				long a = 1;
				for (int j = 0; j < mul.length; j++) {
					if (mul[j].length() > 0) {
						a *= Long.parseLong(mul[j]);
					}
				}
				sp[i] = String.valueOf(a);
			}
		}

		long ans = 0;
		for (int i = 0; i < sp.length; i++) {
			if (sp[i].length() > 0) {
				ans += Long.parseLong(sp[i]);
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}