접미사 표현 식 을 접미사 표현 식 으로 변환 (자바 구현)

우 리 는 평소에 사용 하 는 표준 4 가지 연산 식, 즉 '9 + (3 - 1) * 3 + 10 / 2' 를 접두사 표현 식 이 라 고 합 니 다. 접두사 표현 식 은 역 폴란드 표현 식 이 라 고도 합 니 다. 그 값 을 구 하 는 과정 은 스 택 으로 보조 저장 할 수 있 습 니 다. 프로그램 구현 에 있어 접두사 표현 식 이 쉽게 이 루어 집 니 다. 따라서 접두사 표현 식 을 접두사 표현 식 으로 어떻게 바 꾸 는 지 살 펴 보 겠 습 니 다. 규칙 은 다음 과 같 습 니 다.
먼저 두 개의 데이터 구 조 를 정의 합 니 다.

접미사 표현 식 결 과 를 저장 하 는 문자 StringBuilder

스 택 하나, 연산 자 저장

그리고 접두사 표현 식 을 문자열 로 사용 합 니 다. 표현 식 은 왼쪽 에서 오른쪽으로 한 글자 씩 판단 합 니 다. 규칙 은 다음 과 같 습 니 다.

A. 숫자 라면 StringBuilder

에 직접 저장 합 니 다.

B. 문자 가 ± * / (이면 가감 승제 와 왼쪽 괄호

1. 스 택 이 비어 있 으 면 연산 자 를 스 택 에 직접 넣 습 니 다

2. 현재 의 조작 부 호 는 c 이 고 스 택 꼭대기 의 조작 부 호 는 s 라 고 가정 합 니 다.

c 의 우선 순위 가 s 보다 크 고 스 택 에 직접 들 어 갑 니 다.

c 의 우선 순 위 는 s 보다 작 으 면 s 를 팝 업 합 니 다. 2 로 돌아 가서 조건 a 가 만족 할 때 까지 다시 판단 합 니 다. 만약 에 스 택 이 계속 팝 업 되 고 스 택 이 비 면 조건 1 을 만족 시 키 면 c 를 스 택 에 넣 습 니 다.

스 택 꼭대기 요소 가 (이면 스 택 에 직접 들 어 갑 니 다

C. 문자 가 있다 면), 오른쪽 괄호

왼쪽 괄호

를 만 날 때 까지 스 택 상단 요 소 를 StringBuilder 에 순서대로 추가 합 니 다.

왼쪽 괄호 는 StringBuilder 에 넣 지 않 고 버 립 니 다 (이때 오른쪽 괄호 도 필요 없습니다)

D. 문자 판단 이 끝 난 후에 스 택 이 비어 있 지 않 으 면 스 택 의 요 소 를 StringBuilder

로 순서대로 출력 합 니 다.
사 칙 연산 우선 순위:

더하기 와 빼 기 1

곱 하기 와 나 누 기 2

(왼쪽 괄호 3

오른쪽 괄호 4

주 1: 이 코드 는 잠시 숫자 가 소수 인 상황 을 고려 하지 않 았 습 니 다. 다음 에 주 2: 접미사 표현 식 에 따라 결 과 를 계산 하 는 방법 은 접미사 표현 식 에 따라 결 과 를 계산 하 는 다음 편 을 볼 수 있 습 니 다.
접미사 식 을 접미사 식 으로 변환 하 는 자바 코드 는 다음 과 같 습 니 다.

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static void main(String[] args) {
        System.out.println(calcu("3+4*5+(6*7+8)*9"));
       //    : 345*+67*8+9*+
    }

    //              
    public static String calcu(String s ) {
        Stack<Character> stack = new Stack<>();

        Pattern p = Pattern.compile("\\d");
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Matcher m = p.matcher(c+"");

            //         
            if (m.find()) {
                result.append(c+"");
//                System.out.println(c);
                continue;
            }

            /*      StringBuilder,          
                   ，     
                             ，    ：
               A.      ，    StringBuilder
               B.      +-* /( ,         
                    1.    ，        
                    2.          c,       s
                        a. c      s，    ；
                        b. c        s，  s;   2.       ，    a  
                                   ，    ，    1.  c  ；
                        c.        (,     
               C.      ) ,    
                    1.           StringBuilder，       
                    2.       StringBuilder，    (         )
               D.         ，      ，          StringBuilder
            */
            if (c == '+' || c == '-' || c == '*'
                    || c == '/' || c == '(') {
                if (stack.isEmpty()) {
                    stack.push(c);
                    continue;
                } else {
                    boolean flag = true;
                    while (flag) {
                        if (stack.isEmpty() || conLevel(c) > conLevel(stack.peek()) || stack.peek() == '(') {
                            stack.push(c);
                            flag = false;
                            continue;
                        }

                        if (conLevel(c) <= conLevel(stack.peek())) {
//                            System.out.println(stack.pop());
                            result.append(stack.pop());
                        }
                    }
                }
            }
            if (c == ')') {
                while (stack.peek() != '(') {

//                    System.out.println(stack.pop());
                    result.append(stack.pop());
                }
                stack.pop();  //        ，   
                continue;
            }
        }
        //       ，       
        while (!stack.isEmpty()){
//            System.out.println(stack.pop());
            result.append(stack.pop());
        }

        return result.toString();
    }

    //        
    public static int conLevel (char c) {
        int i = 0;
        switch (c) {
            case '+' :
                i = 1;
                break;
            case '-' :
                i = 1;
                break;
            case '*' :
                i = 2;
                break;
            case '/' :
                i = 2;
                break;
            case '(' :
                i = 3;
                break;
            case ')' :
                i = 0;
                break;
            default: i = -1;
        }
        return i;
    }
}

참고:http://www.nowamagic.net/librarys/veda/detail/2307 https://www.cnblogs.com/zhengxunjie/p/10372329.html