[Java]将算术表达式（中序表达式Infix）转成后续表达式Postfix

时间：2021-07-07 16:52:17

Inlet类：

package com.hy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 此类用于把算术表达式送入解析器
public class Inlet {
    public static void main(String[] args) throws IOException{
        // 取得用户输入的表达式
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String rawExpression = null;
        System.out.print("请输入算术表达式:");
        rawExpression = br.readLine(); 

        // 得到合法的算术表达式
        String expression="";
        for(int i=0;i<rawExpression.length();i++){
            // 拿到表达式的每个字符
            char c=rawExpression.charAt(i);
            //System.out.print(c+","); 

            if(Character.isDigit(c) || c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' ){
                //System.out.print(c);
                expression+=c;
            }else{
                System.out.print(" "+c+"不是合法的算术表达式字符.");
                System.exit(0);
            }
        }

        // 送去解析
        Parser p=new Parser(expression);
        //p.print();

        // 转为后序表达式
        Trans t=new Trans(p.getList());
        t.print();
    }
}

Parser类：

package com.hy;

import java.util.ArrayList;
import java.util.List;

// 此类用于将算术表达式解析成包含操作数和操作符的链表
public class Parser {
    private List<String> list;// 用于存储表达式的链表

    public List<String> getList() {
        return list;
    }

    public Parser(String expression){
        list=new ArrayList<String>();

        String str="";
        for(int i=0;i<expression.length();i++){
            char c=expression.charAt(i);

            if(Character.isDigit(c)){
                str+=c;
            }else{
                if(str.length()>0){// 此判断是因为有+(这种符号相连的情况
                    //System.out.println(str);
                    list.add(str);
                    str="";
                }

                //System.out.println(c);
                list.add(String.valueOf(c));
            }
        }

        if(str.length()>0){// 此判断是因为可能表达式不是以=结尾
            //System.out.println(str);
            list.add(str);
            str="";
        }
    }

    public void print(){
        for(String str:list){
            System.out.println(str);
        }
    }
}

Trans类：

package com.hy;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 此类用于将中序表达式转译成后序表达式
public class Trans {
    private Stack<String> stack;// 用于存储操作符的栈
    private List<String> postfixList;// 用于存储后序表达式的链表

    public Trans(List<String> list){
        stack=new Stack<String>();
        postfixList=new ArrayList<String>();

        for(String str:list){
            // 这个分支是当前项是操作符号的情况
            if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/") || str.equals("(") || str.equals(")")  ){
                String opThis=str;

                if(stack.size()==0){
                    // 如果栈为空，直接把操作符推入栈
                    stack.push(opThis);
                }else if(str.equals("(")){
                    // 如果操作符是左括号，直接推入栈
                    stack.push(opThis);
                }else if(str.equals(")")){
                    // 如果操作符是右括号，则往前找左括号，将左括号之后的操作符放到后续表达式列表中

                    while(stack.peek().equals("(")==false){ // stack.peek()是取栈顶元素而不弹出
                        postfixList.add(stack.pop());
                    }

                    stack.pop();// 左括号丢弃，由此完成了去括号的过程
                }else{
                    // 看栈顶元素，如果它优先级大于等于当前操作符的优先级，则弹出放到后续表达式列表中
                    while( stack.size()>0 && (getOpLevel(stack.peek())>=getOpLevel(opThis)) ){
                        postfixList.add(stack.pop());
                    }

                    stack.push(opThis);// 当前操作符入栈
                }

            }else{
                // 这个分支是当前项是操作数的情况
                postfixList.add(str);// 操作数直接入栈
            }
        }

        // 将栈中余下的操作符弹出放到后续表达式列表中
        while(stack.size()>0){
            String opTop=stack.pop();
            postfixList.add(opTop);
        }
    }

    // 取得操作符的等级
    private int getOpLevel(String op){
        if(op.equals("+") || op.equals("-") ){
            return 0;
        }else if(op.equals("*") || op.equals("/") ){
            return 1;
        }

        return -1;
    }

    public void print(){
        for(String str:postfixList){
            System.out.print(str);
        }
    }
}

执行结果：

请输入算术表达式:1+2-3
12+3-

请输入算术表达式:1+2*3
123*+

请输入算术表达式:2*(3+4)
234+*

请输入算术表达式:1+2*(6-4)
1264-*+

请输入算术表达式:1+2*(5-4)+6-7
1254-*+6+7-

请输入算术表达式:(1+2)*3-4*(6-5)
12+3*465-*-

喝水不忘挖井人，参考资料如下：

1.Java数据结构与算法(第二版) [美]Robert Lafore著

2.栈的应用--中序表达式转后序表达式  https://www.cnblogs.com/bgmind/p/3989808.html

--END--2019年9月2日12点20分

相关文章