괄호 퍼즐 (레벨 3, 강의 4)

많은 JavaRush 생도들 사이에 다양한 감정을 불러일으킨 그러한 작업이 있다고 생각합니다. 9월에 강좌를 시작하면서 과제는 다음과 같이 공식화되었습니다. 1+2*3+4*5+6*7+8*9+10이라는 수식에 괄호 두 쌍을 넣어서 해당 값이 표현식은 537과 같습니다. 이제 솔루션으로 돌아와서 문구가 변경되었음을 발견했습니다. 값이 382가 되도록 표현식 2*3+4*5+6*7에 두 쌍의 괄호를 배치해야 합니다. 물론 새로운 조건은 이전 조건보다 더 간단합니다. 가능한 옵션의 수가 대략 10배 정도 감소했습니다. 그러나 나머지 85개는 수동 검색에 한두 시간을 소비하기에 충분합니다. 분명히 이 작업은 Java 프로그래밍과 직접적인 관련이 없습니다. 그렇기 때문에 해결하지 못했습니다. 이러한 문제에는 추론이나 숫자의 속성을 기반으로 한 분석적 솔루션이 없으며 무차별 대입, 즉 가능한 모든 옵션에 대한 무뚝뚝한 검색만 있습니다. 반면에 이러한 유형의 문제가 프로그래밍의 도움으로 해결된다는 것은 그다지 분명하지 않습니다. 그것이 내가 돌아온 이유이다. 방금 IDE에 익숙해졌고 레벨 8의 코스 문제가 마음을 사로 잡았고 그 문제를 해결하는 데 하루나 이틀 저녁을 보내는 것도 괜찮습니다. 다음은 Java를 사용하여 이 문제를 해결하는 방법입니다. 나는 예제의 기초로 이전 조건을 사용했습니다. 우선, 문자열로 작성된 표현식의 값을 계산하는 방법이 필요합니다. 표준 Java 라이브러리에서는 이러한 메서드를 찾을 수 없습니다. 나는 이것을 검색했습니다: http://www.cyberforum.ru/java-j2se/thread283139.html 은 우리 목적에 매우 적합합니다. 이 알고리즘은 역폴란드 표기법을 기반으로 하며 4개의 산술 연산과 괄호를 포함하는 유효한 문자열에 대해 작동합니다. PPN 클래스가 포함된 새 프로젝트를 만들고 링크의 코드를 복사하여 파일에 붙여넣습니다. 이 문제는 PPN 클래스의 main() 메소드에서 해결될 수 있습니다. 그러나 그것은 필요하지 않습니다. Java 이데올로기는 문제를 작은 하위 작업으로 나누는 데 기반을 두고 있으며, 각 하위 작업은 자체 클래스와 메서드로 구현됩니다. 좋은 접근 방식은 별도의 파일에 저장된 다른 클래스에서 문제를 해결하는 것입니다. 따라서 대괄호 열거 알고리즘을 작성할 다른 클래스를 만듭니다. 문자열 값을 계산하려면 PPN 클래스의 eval() 메서드를 호출해야 합니다. 예를 들어 다음과 같습니다.

System.out.println(PPN.eval(“2*3+4”));

그 쯤

int result = PPN.eval(s2);

1+2*3+4*5+6*7+8*9+10 줄을 자세히 살펴보고 여는 괄호를 몇 가지 방법으로 넣을 수 있는지 자문해 봅시다. 10가지 방법으로 배치할 수 있습니다. 0부터 시작하여 문자열 문자의 번호를 매기면 여는 괄호를 {0,2,4,6,8,10,12,14,16,18} 위치에 배치할 수 있습니다. 예를 들어, 6번째 위치에 괄호를 배치한다는 것은 0부터 5까지의 모든 문자를 가져와서 괄호를 넣은 다음 6번째부터 줄 끝까지의 모든 문자를 가져와야 함을 의미합니다. 마찬가지로 닫는 괄호는 {1,3,5,7,9,11,13,15,17,20} 위치에 배치할 수 있습니다. 마지막 두 숫자는 라즈베리 전체를 망치고 다른 모든 위치는 서로 2만큼, 17과 20은 3만큼 다릅니다. 따라서 단순히 닫는 괄호의 위치 번호를 포함하는 변수를 선언하고 다음 단계마다 그 값을 2씩 증가시키는 것은 불가능합니다. 위치 값을 배열에 저장합니다.

int[] left = {0,2,4,6,8,10,12,14,16,18};

int[] right = {1,3,5,7,9,11,13,15,17,20};

그리고 옵션 열거를 담당하는 루프를 반복할 때마다 인덱스 변수를 1씩 증가시킵니다. 전체적으로 두 개의 여는 괄호와 두 개의 닫는 괄호가 각각 필요하며 4개의 인덱스 변수가 필요합니다.

int indLeft1, indLeft2, indRight1, indRight2;

표현식의 괄호는 두 가지 방법으로 배치할 수 있습니다.

(  )  (  )
(  (  )   )

각 방법에 대해 자신만의 알고리즘을 작성해야 합니다. 대괄호를 정렬하는 첫 번째 방법에 대한 알고리즘을 고려하세요. 옵션의 실제 열거는 중첩된 for 루프로 표시됩니다.

for (int indLeft1=0;indLeft1<10;indLeft1++)
   for(int indRight1=indLeft1+1;indRight1<10;indRight1++)
      for (int indLeft2=indRight1+1;indLeft2<10;indLeft2++)
         for (int indRight2=indLeft2+1;indRight2<10;indRight2++)

프로그램 시작 부분에서 괄호 없이 원래 문자열로 문자열 변수를 초기화합니다.

String s = "1+2*3+4*5+6*7+8*9+10";

내부 루프의 본문에서 대괄호로 한 줄을 만듭니다.

String s2 = s.substring(0, left[indLeft1]) + "(" +
		 s.substring(left[indLeft1], right[indRight1]) + ")" +
		 s.substring(right[indRight1],left[indLeft2]) + "(" +
		 s.substring(left[indLeft2], right[indRight2]) + ")" +
		 s.substring(right[indRight2], s.length());

String 클래스의 substring() 메서드의 특성에 주의하세요. 하위 문자열이 선택됩니다. 첫 번째 문자의 수는 첫 번째 매개변수와 같고, 마지막 문자의 수는 두 번째 매개변수에서 1을 뺀 것과 같습니다 . https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) 을 참조하세요 . 오해를 줄이기 위한 예제도 있습니다. 대괄호로 문자열을 만든 후 값을 계산하고 필요한 값과 비교합니다.

int result = PPN.eval(s2);
if (result == 537)
          System.out.println(s2);

중첩된 괄호 배열을 위한 블록도 비슷한 방식으로 작성됩니다. 내가 주목하고 싶은 유일한 점은 괄호가 중첩될 때 여는 괄호와 닫는 괄호가 같은 위치에 있을 수 있다는 것입니다. 예를 들어

1+((2*3+4*5+6)*7+8*9+10)

또는

(1+2*(3+4*5+6*7+8))*9+10

사실 그게 전부입니다. 실행 후, 올바르게 작성된 프로그램은 다음과 같은 단일 답을 생성합니다: 1+2*(3+4*(5+6*7)+8*9)+10