Java利用 后序表达式 实现计算器功能

java利用逆波兰表达式（后序表达式）计算结果

1.前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。比如:- × + 3 4 5 6
2.中缀表达式就是常见的运算表达式，如(3+4)×5-6
3.后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后,比如:3 4 + 5 × 6 -

这里说一下大概实现的步骤：

1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2;
2. 从左至右扫描中缀表达式；
3. 遇到操作数（操作数就是数字）时，直接压入s2;
4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
   1)如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；
   2)否则，做优先级比栈顶运算符的高，也将运算符压入s1；
   3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到（4.1）与s1中新的栈顶运算符相比较
5. 遇到括号时：
   1)如果时左括号“（”，则直接压入s1
   2)如果是右括号“）”，则一次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6. 重复步骤2-5，直到表达式的最右边；
7. 将s1中剩余的运算符一次弹出并压入s2；
8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

代码实现的计算机在输入的字符串的时候是可以加小括号的。

具体的功能和流程,代码里的注释写的很清楚了:

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

/**
 * 利用逆波兰表达式（后序表达式）计算结果
 */
public class PolandNotation {
    public static void main(String[] args) {
        
        //将用户输入的字符串转化为 集合（ArrayList）类型的  方便后面栈的操作
        //   “(3+4)*5-2”   --> “[(,3,+,4,),*,5,-,2]”
        String s = "(3+4)*5-2";
        //将字符串转化为集合
        List<String> sl = toInfixExpressionList(s);
        System.out.println("将字符串 转化为 集合类型后的结果为：" + sl);
        //将集合转化为后缀表达式
        List<String> s2 = parseSuffixExpreesionList(sl);
        System.out.println("转化为后缀表达式的结果为：" + s2);
        //计算后缀表达式的结果
        int res=calculator(s2);
        System.out.printf("最后的运算结果是：%d",res);

    }

    //将用户输入的字符串转化为 集合（ArrayList）类型的  方便后面栈的操作
    //      “（3+4）*5-2”   --> “[（,3,+,4,）,*,5,-,2]”
    public static List<String> toInfixExpressionList(String s) {
        List<String> list = new ArrayList<String>();
        int index = 0;  //索引，相当于指向字符串每一个元素的指针
        char c;  //将字符串中取出的元素付给c
        while (index < s.length()) {
            //首先判断c是不是数字
            if ((c = s.charAt(index)) < 48 || (c = s.charAt(index)) > 57) {
                //如果不是数字 直接将其加入到集合里面
                list.add("" + c);
                index++;
            } else {
                //如果是数字的话，需要判断是不是多位数
                //如果是多位数的话，将多位数转化为String
                String num = "";
                while (index < s.length() && (c = s.charAt(index)) >= 48 && (c = s.charAt(index)) <= 57) {
                    num += c;
                    index++;
                }
                list.add(num);
            }
        }
        return list;
    }


    /**
     * 1.初始化两个栈：运算符栈s1和储存中间结果的栈s2;
     * 2.从左至右扫描中缀表达式；
     * 3.遇到操作数（操作数就是数字）时，直接压入s2;
     * 4.遇到运算符时，比较其与s1栈顶运算符的优先级：
     * 1)如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；
     * 2)否则，做优先级比栈顶运算符的高，也将运算符压入s1；
     * 3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到（4.1）与s1中新的栈顶运算符相比较
     * 5.遇到括号时：
     * 1)如果时左括号“（”，则直接压入s1
     * 2)如果是右括号“）”，则一次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 6.重复步骤2-5，直到表达式的最右边；
     * 7.将s1中剩余的运算符一次弹出并压入s2；
     * 8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     */
    public static List<String> parseSuffixExpreesionList(List<String> ls) {

        Stack<String> s1 = new Stack<String>();
        List<String> s2 = new ArrayList<String>();
        for (String item : ls) {
            if (item.matches("\\d+")) {
                s2.add(item);
            }else if(s1.empty()){
                s1.push(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();
            } else if (Operation.getValue(s1.peek()) < Operation.getValue(item)) {
                s1.push(item);
            } else if (Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                do {
                    s2.add(s1.pop());
                } while (!s1.empty()&&Operation.getValue(s1.peek()) >= Operation.getValue(item));
                s1.push(item);
            } else {
                System.out.println("输入的字符有误");
            }
        }
        for (String s:s1){
            s2.add(s);
        }
        return s2;
    }




    //计算，算出 后缀表达式 的结果
    public static int calculator(List<String> list) {

        Stack<String> stack = new Stack<String>();
        for (String item : list) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")||item.equals("x")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("输入的符号不正确");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

}

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 s) {
        if (s.equals("+")) {
            return ADD;
        } else if (s.equals("-")) {
            return SUB;
        } else if (s.equals("*")||s.equals("x")) {
            return MUL;
        } else if (s.equals("/")) {
            return DIV;
        }else if(s.equals("(")){
            return 0;
        } else{
            System.out.println("没有该运算符！");
        }
        return 0;
    }
}