글 읽기 - 후위표기법 - 18%에서 오류나는데 반례좀 찾아주세요.(설명 자세히 올렸습니다)

gunflake09 6년 전 0

채점 18%에서 오류가 발생해서 틀렸다고 하는데, 어떤 부분이 틀린지 잘 모르겠습니다.

후위표기법 구성은

1. 연산자, 괄호, 알파벳으로 구분한 후

2. 연산자가 들어왔을 때, stack이 비어있으면 현재 연산자를 Stack에 추가

2-1. 연산자가 '+', '-' 일 경우, stack의 top이 '*', '/' 이라면

'(' 혹은 스택이 빌때까지 pop을 하여 string에 추가한다. 그 후 스택에 현재 연산자를 추가한다

2-2. 연산자가 '*', '/'일 경우, stack에 추가한다.

3-1. 괄호가 '('일 경우 스택에 추가한다.

3-2 괄호가 ')'일 경우 '('를 만나기 전까지 pop하여 string에 추가한다. 그 후 '(' 를 스택에서 제거한다.

이렇게 알고리즘을 구현했습니다. 코드에 주석 달아놨습니다.

어떤 부분에서 반례가 생기는지 잘 모르겠습니다.

a+b*c+d 인 경우 abc*+d+ 로 출력됩니다.

질문 해결좀 부탁드립니다. 감사합니다

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static final int operator = 11;        //연산자, 괄호, 알파벳 비교를 위해 final 선언
    public static final int parentheses = 22;
    public static final int alphabet = 33;
    public static final int plus = 43;        
    public static final int minus = 45;
    public static final int multiplier = 42;
    public static final int divider = 47;
    public static final int left_parentheses = 40;
    public static final int right_parentheses = 41;

    public static Stack<Character> operator_stack = new Stack<>();


    public static int match_Char(char a) { //String의 char를 연산자, 괄호, 알파벳으로 구분해주는 함수

        if (a == '+' || a == '-' || a == '*' || a == '/')
            return operator;
        else if (a == '(' || a == ')')
            return parentheses;
        else
            return alphabet;
    }

    public static String postfix_Notation(String input) { //input String을 후위표기법으로 바꿔주는 함수
        String result = "";

        for (int i = 0; i < input.length(); i++) {
            if (match_Char(input.charAt(i)) == operator) { //연산자일 경우

                if (operator_stack.isEmpty())              //스택이 비어 있으면 연산자를 stack에 push한다
                    operator_stack.add(input.charAt(i));
                else {                                     //스택이 비어있지 않다면

                    if (input.charAt(i) == plus || input.charAt(i) == minus) {  //연산자가 '+' 혹은 '-' 일경우
                        if ( operator_stack.peek() == divider
                                || operator_stack.peek() == multiplier) { //top이 '/' , '*' 일 경우
                                                                          //'('혹은 emptyStack이 될때까지 stack의 연산자를 pop한 후 현재 연산자를 push한다

                            while(!operator_stack.isEmpty()) {
                                if(operator_stack.peek()=='(')
                                    break;
                                result += operator_stack.pop();
                            }


                            operator_stack.add(input.charAt(i));
                        } else {
                            operator_stack.add(input.charAt(i));
                        }
                    } else {                        //연산자가 '*', '/'일 경우 stack에 push한다
                        operator_stack.add(input.charAt(i));
                    }
                }

            } else if (match_Char(input.charAt(i)) == parentheses) {

                if(input.charAt(i)==left_parentheses) //괄호가 '('면 스택에 추가 
                    operator_stack.add(input.charAt(i));
                
                else if(input.charAt(i)==right_parentheses){ //괄호가 ')'이면 
                    while(operator_stack.peek()!=left_parentheses){ //'('을 만나기 전까지 pop한다 
                        result+=operator_stack.pop();
                    }
                    operator_stack.pop(); //'(' 괄호 제거
                }

            } else if(match_Char(input.charAt(i)) == alphabet) {
                result += input.charAt(i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String postfix_str = postfix_Notation(input);

        while (!operator_stack.isEmpty())
            postfix_str += operator_stack.pop();
        System.out.println(postfix_str);

    }
}

ho94949 6년 전 3

A*B*C*D를 입력으로 넣었을 때 ABCD***이 나오네요

AB*C*D*가 나와야 할 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

후위표기법 - 18%에서 오류나는데 반례좀 찾아주세요.(설명 자세히 올렸습니다)

gunflake09 6년 전 0

ho94949 6년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말