데이터 구조의 접미사 표현 식 접미사 표현 식(자바 구현)

이전 글 에 서 는 자바 로 접미사 표현 식 의 계산,링크 를 실현 하 였 습 니 다.https://blog.csdn.net/xindanding/article/details/90443998
하지만 우리 가 계산 할 때 계산 할 표현 식 을 수 동 으로 접미사 로 바 꾸 어 계산기 에 버 릴 수 는 없 잖 아 요.그러면 계산기 가 왜 요?그 렇 죠?
다음은 접미사 표현 식 을 접미사 표현 식 으로 바 꾸 는 방법 입 니 다.
우선,노드 를 만 듭 니 다.  
//노드 는 연산 자 를 저장 하 는 데 사 용 됩 니 다.이것 은 접미사 식 의 계산 과 다 릅 니 다.

public class SignNode {
    String signName;
    SignNode next;

    public String getSignName() {
        return signName;
    }

    public void setSignName(String signName) {
        this.signName = signName;
    }

    public SignNode getNext() {
        return next;
    }

    public void setNext(SignNode next) {
        this.next = next;
    }
}

그 다음 에 우 리 는 연산 자 를 관리 하 는 링크 를 만 들 었 다.
//연산 자의 출입 을 제어 하 는 데 주로 사 용 됩 니 다.

public class SignList {
    private SignNode list;
    private int length;

    public SignNode element(){
        return list;
    }

    public SignNode pop(){
        SignNode signNode = new SignNode();
        signNode = list;
        list = list.next;
        length --;
        return signNode;
    }

    public void push(SignNode signNode){
        signNode.next = list;
        list = signNode;
        length ++;
    }

    public SignNode getList() {
        return list;
    }

    public void setList(SignNode list) {
        this.list = list;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }
}

다음은 진짜 조작 과 테스트 입 니 다.

public class Main {

    private static Map signMap = new HashMap();   //         
    private static String signCol = "+-*/()";

    static {
        signMap.put("+", 1);
        signMap.put("-", 1);
        signMap.put("*", 4);
        signMap.put("/", 4);
        signMap.put("(", 0);       //                （3*2-3）
    }

    public static void main(String[] args) {
        infix2suffix();
    }

    private static void infix2suffix(){
//        String str = "9,+,(,3,-,1,),*,3,+,10,/,2";
        String str = "9,+,(,3,*,2,-,3,),*,3,+,10,/,2";

        SignList signList = new SignList();
        String[] exp = str.split(",");
        List result = new ArrayList();

        for(int i = 0; i < exp.length; i++){
            if(signCol.contains(exp[i])){
                if("(".equals(exp[i])){     //   （    
                    SignNode node = new SignNode();
                    node.setSignName(exp[i]);
                    signList.push(node);
                }else if(")".equals(exp[i])){
                    popStack(signList, result);
                } else {
                    pushOrPopStack(signList, exp[i], result);
                }
            }else{   //            
                result.add(exp[i]);
            }
        }

        while(signList.getLength() > 0){
            SignNode node = signList.pop();
            result.add(node.getSignName());
        }

        System.out.println(result);


    }

    private static void popStack(SignList signList, List result){
        SignNode node = signList.pop(); //       
        if(!"(".equals(node.getSignName())){ //           （       
            result.add(node.getSignName());
            popStack(signList, result);   //          
        }
    }

    private static void pushOrPopStack(SignList signList, String val, List result){

        if(signList.getLength() != 0) {     //      

            SignNode stackTop = signList.element();             //      
            if (signMap.get(stackTop.getSignName()) < signMap.get(val)) {      //         ，   
                SignNode signNode = new SignNode();
                signNode.setSignName(val);
                signList.push(signNode);
            }else{      //         
                SignNode node = signList.pop();
                result.add(node.getSignName());     //             
                pushOrPopStack(signList, val, result);   //             
            }

        }else{      //            
            SignNode node = new SignNode();
            node.setSignName(val);
            signList.push(node);
        }

    }

결과:[9,3,2,*,3,-,3,*,+,10,2,/,+]
만약 고려 하지 않 은 것 이 있다 면,모두 가 지적 해 주시 기 바 랍 니 다.