역 폴란드 식 (접미사 식) 의 계산 & 접미사 식 접미사 식 (역 폴란드 식) [자바 구현]

역 폴란드 식 계산
생각:

*  1.         
*  2.          ，   stack
*  3.           ，stack      ，num2 num1,              
*  4.         
*  5.                 

코드
들 어 오 는 역 폴란드 표현 식 은: 4 5 * 8 - 60 + 8 2 / +         접미사 식  4 * 5 - 8 + 60 + 8 / 2
결과: 76
역 폴란드 표현 식 이 역 폴란드 집합 으로 바 뀌 었 다.

/**
     *          
     * @param express       （     ）
     * @return
     */
    public static List expressToArrayLisy(String express){
        String[] split = express.split(" ");
        List list = new ArrayList<>();
        for (String s : split) {
            list.add(s);
        }
        return list;
    }

 
역 폴란드 식 계산

 /**
     *          
     *   :
     *  1.         
     *  2.          ，   stack
     *  3.           ，stack      ，num2 num1,              
     *  4.         
     *  5.                 
     *   stack.pop()    
     * @param list          
     * @return
     */
    public static int polandCal(List list){
        Stack stack = new Stack();
        for (String item : list) {
            //        ，     
            if(item.matches("\\d+")){
                stack.push(item);
            }else{
                //       
                Integer num2 = Integer.parseInt(stack.pop());
                Integer num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if(item.equals("+")){
                    res = num2 + num1;
                }else if(item.equals("-")){
                    res = num1 - num2;
                }else if(item.equals("*")){
                    res = num1 * num2;
                }else if(item.equals("/")){
                    res = num1 / num2;
                }else{
                    throw new RuntimeException("     ...");
                }
                stack.push(res+"");
            }
        }
        return Integer.parseInt(stack.pop());
    }

2. 접미사 식 접미사 식 (역 폴란드 식)
접미사 표현 식: 1 + ((2 + 3) * 4) - 5 
접미사 식 집합: [1, +, (, (, 2, +, 3,), *, 4,), -, 5]
접미사 표현 식: [1, 2, 3, +, 4, *, +, 5, -]
접미사 식 계산 결과: 16
생각:
1. 접미사 표현 식 을 접미사 표현 식 집합 으로 전환 합 니 다.여기 서 전환 할 때 여러 비트 의 처리 에 주의 하 세 요.
2. 접두사 표현 식 을 옮 겨 다 니 며 집합 합 니 다.연산 자 스 택 stack, 결 과 를 저장 하 는 집합 list 를 준비 합 니 다.
3. 왼쪽 에서 오른쪽으로, 숫자 일 때 집합 에 추가
4. 괄호 일 때 두 가지 상황 으로 나눈다
    4.1 만약 에 (왼쪽 괄호 라면 바로 창고 에 들어간다.
    4.2 만약 에) 오른쪽 괄호 라면 stack 에 있 는 요 소 를 순서대로 꺼 내 list 에 넣 고 (왼쪽 괄호 를 만 날 때 까지 이 괄호 를 잃 어 버 립 니 다.
5. 연산 자 일 때 다음 과 같은 상황 으로 나 뉜 다.
    5.1 stack 이 비어 있 거나 스 택 꼭대기 요소 가 (왼쪽 괄호 일 경우 스 택 에 직접 들 어 갑 니 다.
    5.2 만약 에 이때 연산 자의 우선 순위 가 스 택 꼭대기 요소 연산 자의 우선 순위 보다 크 면 바로 스 택 에 들어간다.
    5.3 이때 연산 자의 우선 순위 가 스 택 상단 요소 연산 자의 우선 순위 보다 작 으 면 stack 의 스 택 상단 요소 pop 을 팝 업 하여 list 에 추가 합 니 다. 스 택 이 비어 있 거나 이때 까지 연산 자의 우선 순위 가 스 택 상단 요소 연산 자의 우선 순위 보다 클 때 까지 스 택 에 들 어 갑 니 다.
6. 표현 식 의 맨 오른쪽 까지 3 - 5 반복
7. stack 의 요 소 를 모두 팝 업 하여 list 에 추가 합 니 다.
8. 이때 list 결합 은 접미사 표현 식 (역 폴란드 식) 입 니 다.
 
코드
접미사 식 문자열 접미사 식 집합

 /**
     *                     
     * @param express      
     * @return
     */
    public static List toInfixExpressionList(String express){
        List list = new ArrayList<>();
        int length = express.length();
        int i = 0;
        char c ;
        String str = "";
        do{
            if(( c = express.charAt(i)) < 48 || ( c = express.charAt(i)) > 57){
                list.add(c+"");
                i++;
            }else{
                //         
                str = "";//   
                //   ASII ，48      0 57     9
                while(i < length && (c = express.charAt(i)) >=48 && (c = express.charAt(i)) <= 57){
                    str+=c;
                    i++;
                }
                list.add(str);
            }
        }while(i < length);
        return list;
    }

연산 자의 우선 순위 가 져 오기

//      ，           
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation){
        int result = 0;
        switch (operation){
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
            default:
                System.out.println("       ");
                break;
        }
        return result;
    }
}

접미사 식 접미사 식

/**
     *             
     * @param infixExpressionList         
     * @return      
     */
    public static List parseSuffixExpressionList(List infixExpressionList){
        Stack stack = new Stack<>();
        List list = new ArrayList<>();

        for (String item : infixExpressionList) {
            //  item    ，      
            if(item.matches("\\d+")){
                list.add(item);
            }else if(item.equals("(")){
                //  item  （     ，    
                stack.push(item);
            }else if(item.equals(")")){
                //      
                //  item ）    ，     stack      ，   list ，    （     ，          
                while(!stack.peek().equals("(")){
                    list.add(stack.pop());
                }
                stack.pop();//  （     
            }else{
                //        
                while(stack.size() != 0 && Operation.getValue(item) <= Operation.getValue(stack.peek())){
                    list.add(stack.pop());
                }
                stack.push(item);
            }
        }
        //  stack         list 
        while(stack.size() > 0){
            list.add(stack.pop());
        }
        return list;
    }

 
마지막 으로 한 문 제 를 풀 고 다른 곳 에서 참고 한 것 이다.https://blog.csdn.net/fascinatingGirl/article/details/52447647?utm_source=blogxgwz9
접미사 표현 식 X = A + B * (C - (D + F)) / E 접미사 표현 식 다음은 무엇 입 니까?

A.ABCDF+-*E/+

B.ABDF+C-*E/+

C.ABDF+C*-E/+

D.ABDF+C*-E+/

정 답: A
A+B*(C-(D+F))/E
1. A 를 읽 고 A 를 직접 출력 합 니 다.
2, 읽 기 +, 창고 에 넣 기
3. B 까지 읽 고 직접 출력 합 니 다. 이때 스 택 에 +, 출력 AB 가 있 습 니 다.
4. * 까지 읽 습 니 다. * 의 우선 순위 가 + 보다 높 기 때문에 스 택 에 들 어가 면 + * (오른쪽 은 스 택 꼭대기) 가 있 습 니 다.
5, 읽 기 (, 우선 순위 가 가장 높 고, 만 남) 에서 나 옵 니 다. 창고 에 들 어가 면 + * (
6. C 까지 읽 고 ABC 출력
7, 읽 기 -, 창고 에 들 어가 고, 창고 에 + * 가 있 습 니 다. （ —
8, 읽 기 (, 스 택 에 들 어가 고, 스 택 에 + 가 있 습 니 다. *  （  —（
9, D 까지 읽 고 ABCD 출력
10. 읽 기 +, 스 택 에 들 어가 기, 스 택 에 + 가 있 습 니 다. *  （  —（ +
11. F 까지 읽 고 ABCDF 출력
12, 읽 기), 스 택 +, 출력 ABCDF +, 스 택 에 + *  （ —
13. 읽 기), 스 택 나 가기 -. 출력 ABCDF + -, 스 택 에 + 가 있 습 니 다. *
14. 읽 기 /, 스 택 *, 스 택 에 들 어가 기 /, 출력 ABCDF + - *, 스 택 에 + /
15, 읽 기 E, 출력 ABCDF + - * E
15, 스 택 /, 출력 ABCDF + - * E /
16, 스 택 +, 출력 ABCDF + - * E / +
그래서 접미사 표현 식 은 ABCDF + - * E / + 입 니 다.