자바 RPN (역 폴란드 표기법) 중위 '('나는 스택은 PRN 및 구축에 사용되는 것을 확신

Question

을 접미사에하기는 무시됩니다,하지만 경우 될 것 같지 않습니다 예를 들면 다음과 같습니다.

• 입력 1 52+ (1 + 2) * 4-3
• 입력 2 52 + (+ 2 (1) * 4) -3-
• 입력 3 (52 + 1 +2) * 4-3

입력 1과 입력 2 출력은 같아야하고 입력 1과 입력 3은 달라야합니다.

• 출력 1 52 1 2 + 4 - 3 * +
• 출력 2 52 1 2 + 4 * 3 - +
• 출력 3 52 1 2 + 4 3 - * +

    public static String Infix2(String input) { 
     char[] in = input.toCharArray(); 
     Stack<Character> stack = new Stack<Character>(); 
     StringBuilder out = new StringBuilder(); 

     for (int i = 0; i < in.length; i++) 
      switch (in[i]) { 
      case '+': 
      case '*': 
      case '-': 
       out.append(' '); 
       stack.push(in[i]); 
       break; 
      case ' ': 
      case '(': 
       break; 
      case ')': 
       out.append(' '); 
       out.append(stack.pop()); 
       break; 
      default: 
       out.append(in[i]); 
       break; 
      } 

     while (!stack.isEmpty()) { 
      out.append(' '); 
      out.append(stack.pop()); 
     } 

     return out.toString(); 
    } 

내가 입력 1 및 제 3 일하고 싶어한다고 가정하면, 내가 어떤 방법을 사용 하는가?

편집 : '+', '-', '*'및 '/'가 변경되면 해당 입력에 적용됩니다.

public static String Infix2(String input) { 
    if (input == null) 
     return ""; 
    char[] in = input.toCharArray(); 
    Stack<Character> stack = new Stack<Character>(); 
    StringBuilder out = new StringBuilder(); 

    for (int i = 0; i < in.length; i++) 
     switch (in[i]) { 
     case '+': 
     case '-': 
      while (!stack.empty() 
        && (stack.peek() == '*' || stack.peek() == '/')) 
       out.append(' ').append(stack.pop()); 
     case '*': 
     case '/': 
      out.append(' '); 
     case '(': 
      stack.push(in[i]); 
     case ' ': 
      break; 
     case ')': 
      while (!stack.empty() && stack.peek() != '(') 
       out.append(' ').append(stack.pop()); 
      if (!stack.empty()) 
       stack.pop(); 
      break; 
     default: 
      out.append(in[i]); 
      break; 
     } 

    while (!stack.isEmpty()) 
     out.append(' ').append(stack.pop()); 

    return out.toString(); 
} 

Answer 1

알고리즘은 매우 간단합니다 (및 here is a good explanation). 모든 연산은 +와 -가 가장 낮은 결합 가중치를가집니다.

• 밖으로 인쇄 번호는 왼쪽에 충돌 할 때까지 즉시
• 는
• 바로 괄호가 스택에서 팝
• 왼쪽 괄호가 스택에 가서 무거운 항목에 가벼운 항목을 넣어 결코 : 두 가지 규칙이 있습니다
  : 괄호 다음

첫 번째 예를 감안할 때 왼쪽 괄호, 52+ (1 + 2) * 4-3을 제거, 여기 스택입니다 0

52+   => + 
52+(  => + (
52+(1+  => + (+ 
52+(1+2)  => +  //right parentheses popped + 
52+(1+2)*4 => + * 
52+(1+2)*4-3 => + -  //can't put - on top of *, so pop off * 
... and then pop the stack until it's empty. 

스위치 루프를 다음과 같이 바꾸면 (세 번째 예제와 가장 유사) 세 가지 예에 대해 올바른 답을 얻을 수 있습니다. 실제 파서에서는 각 연산자에게 가중치를 부여하고 팝 메커니즘을 일반화합니다.

for (int i = 0; i < in.length; i++) 
     switch (in[i]) { 
     case '+': 
     case '-': 
      while (!stack.empty() && (stack.peek() == '*' || stack.peek() == '/')) { 
       out.append(' '); 
       out.append(stack.pop()); 
      } 
      out.append(' '); 
      stack.push(in[i]); 
      break; 
     case '*': 
     case '/': 
      out.append(' '); 
      stack.push(in[i]); 
      break; 
     case '(': 
      stack.push(in[i]); 
      break; 
     case ')': 
      while (!stack.empty() && stack.peek() != '(') { 
       out.append(' '); 
       out.append(stack.pop()); 
      } 
      stack.pop(); 
      break; 
     default: 
      out.append(in[i]); 
      break; 
     } 

Answer 2

아니 특정 질문하지만 알고리즘 이러한 종류의 개발을위한 권하고 싶습니다 무엇인가에 대한 정확한 대답은 : 테스트 기반으로 개발되어 (TDD)를 보라. 간단히 말해서, infix2 메소드가 테스트 패턴 (표현식)을 제공하고 테스트 할 때 infix2 메소드가 올바른 출력을 생성하는 경우, 몇 가지 유닛 테스트 (예 : JUnit)를 작성하십시오.

String[] illegalExpressions = {null, "", " ", "1 +", "1 + 1)"}; 

같은

assertequals("1", "1"); // positive number 
assertequals("-1", "-1"); // negative number 
assertequals("1+1", "1 1 +"); // simple addition 
assertequals(" 1 + 1 ", "1 1 +"); // simple addition with whitechars 
assertequals(" 1 + +1 ", "1 -1 +"); // simple addition with pos. number & whitechars 
assertequals(" 1 + -1 ", "1 -1 +"); // simple addition with neg. number & whitechars 
assertequals("(1+1)", "1 1 +"); // simple addition with brackets 

같은

쉽게 사람과

시작을 잊지 마세요 불법 식을 당신을 위해 테스트 케이스는 예

assertequals("52+(1+2)*4-3", "52 1 2 + 4 * 3 -"); 
assertequals("52+((1+2)*4)-3", "52 1 2 + 4 * 3 -"); 
assertequals("(52+1+2)*4-3", "52 1 + 2 + 4 * 3 -");