用栈的数据结构实现综合计算器含中缀后缀计算及转换计算

用栈实现综合计算器

1. 实现中缀表达式的综合计算器

不带()的综合计算器：

思路及源码：

import java.util.Stack;

public class 用双栈实现简单运算 {
    //运算 栈先弹出num1
    public static int cal(int num1, int num2, int oper) {
        int res = 0;
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;//注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;//
                break;
        }
        return res;
    }
    //判断是否操作符
    public static boolean isOper(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
    //运算符优先级（数字越大优先级越高）
    public static int priority(int oper){
        if(oper == '*' || oper == '/'){
            return 1;
        }else if (oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1;//非运算符
        }
    }
    //对输入的字符串进行计算
    public static int sum(String str){
        if(str == null || str.length()==0){
            return -1;
        }
        //存放操作数的栈
        Stack<Integer> data = new Stack<>();
        //存放操作符的栈
        Stack<Character> oper = new Stack<>();

        int index = 0;
        int start;
        while(index < str.length()){
            start = index;
            char c = str.charAt(index);
            if(!isOper(c)){ //如果是操作数入操作数栈
                while(index< str.length() && !isOper(str.charAt(index))){
                    index++;
                }
                String s = str.substring(start, index);
                int d = Integer.parseInt(s);
                data.push(d);
            }else{
                //是操作符
                // 1. 如果操作符栈为空入栈
                if(oper.isEmpty()){
                    oper.push(c);
                }else{
                    //2. 判断栈顶与当前操作符优先集
                    Character c1 = oper.peek();
                    int p1 = priority(c1);// 栈顶优先级
                    int p2 = priority(c);//  当前操作符优先级
                    // 数字越大优先级越高
                    //2.1 如果栈顶优先级<= 当前操作符优先级，则直接入栈
                    if(p1 <= p2)
                        oper.push(c);
                    else{//2.2 先运算在把结果入操作数栈，pop两个操作数，和栈顶操作符，再把当前操作符入操作符栈
                        Character op = oper.pop();
                        int num1 = data.pop();
                        int num2 = data.pop();
                        //运算
                        int res = cal(num1,num2,op);
                        //分别入栈
                        data.push(res);
                        oper.push(c);
                    }
                }
                index ++;
            }
        }
        //当操作符栈不为空时继续运算得到最终结果
        if(!data.isEmpty() && !oper.isEmpty()){
            int num1= data.pop();
            int num2 = data.pop();
            char op = oper.pop();
            int res = cal(num1,num2,op);
            data.push(res);
        }
        return data.peek();//最终结果
    }

    public static void main(String[] args) {
        String str = "60*2-20";
        System.out.println(sum(str));
    }
}

2. 逆波兰计算器

1. 给定一个后缀表达式完成计算

思路：

1. 操作数直接入栈
2. 遇到操作符，两个操作数出栈，进行运算，运算结果入栈
3. 直到到表达式最后结束否则重复上面的操作

思路及源码：

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

public class 后缀表达式的运算 {

    public static void main(String[] args) {
        //给定后缀表达式
        String str = "3 40 +";//如何得到呢
        //把后缀表达式存入List
        List<String> list = getList(str);
        int cal = cal(list);
        System.out.println("后缀表达式 " + str + "的结果= " + cal);
    }

    //运算
    private static int cal(List<String> list) {
        //栈存操作数
        Stack<String> stack = new Stack<>();
        while (list.size() > 0) {
            //从左往右计算，如果是操作数入栈
            if (list.get(0).matches("[0-9]+")) {
                stack.push(list.remove(0));
            } else {
                //操作数出栈运算
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                //当前这个数是操作符
                String oper = list.remove(0);
                //根据操作符运算
                int res = 0;
                if (oper.equals("+")) {
                    res = num1 + num2;
                } else if (oper.equals("-")) {//注意顺序
                    res = num2 - num1;
                } else if (oper.equals("*")) {
                    res = num1 * num2;
                } else {
                    res = num2 / num1;
                }
                stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.peek());
    }

    //把后缀表达式存到list
    private static List<String> getList(String str) {
        String[] s = str.split(" ");
        ArrayList<String> list = new ArrayList<>();
        for (String tmp : s) {
            list.add(tmp);
        }
        return list;
    }
}

2. 中缀表达式转后缀表达式

中缀表达式便于人的书写计算，而计算习惯后缀表达式计算

具体操作：

代码实现：

import java.util.Stack;

public class 中缀转后缀 {
    public static String infixToSuffix(String infix) {
        // 1. 建立两个栈
        //操作符栈
        Stack<Character> data = new Stack<>();
        //最终结果栈用StringBuffer代替
        StringBuffer sb = new StringBuffer();
        //2. 建立指针遍历字符串
        int index = 0;
        int start;
        while (index < infix.length()) {
            start = index;
            char c = infix.charAt(index);
            if (String.valueOf(c).matches("[0-9]+")) {//如果为数字直接入结果栈
                while (index < infix.length() && String.valueOf(infix.charAt(index)).matches("[0-9]+")) {
                    index++;
                }
                String s = infix.substring(start, index);
                sb.append(s);
                if (index <= infix.length())
                    sb.append(" ");//间隔空格以区分数字,最后不要多余的空格
            } else if (c == '(') {//如果为（ （ () 不是运算符单独处理）
                data.push(c);
                index++;
            } else if (c == ')') {//如果为）
                while (data.peek() != '(') {
                    sb.append(data.pop());
                    sb.append(" ");
                }
                data.pop();//pop左括号
                index++;
            } else {
                // 是操作符了
                // 判断如果栈为空或者栈顶为（直接入栈
                if (data.isEmpty() || data.peek() == '(') {
                    data.push(c);
                } else {
                    // 判断优先级
                    int ptop = priority(data.peek());//栈顶优先级
                    int p = priority(c);//当前数优先级
                    if (p > ptop) {//如果当前运算符优先级高于栈顶元素
                        data.push(c);
                    } else {
                        while (p <= ptop) {
                            sb.append(data.pop());
                            sb.append(" ");
                            if (!data.isEmpty()) {
                                ptop = priority(data.peek());
                            } else
                                break;
                        }
                        data.push(c);
                    }
                }
                index++;
            }
        }
        while (!data.isEmpty()) {
            int count = 1;
            sb.append(data.pop());
            if (count < data.size())
                sb.append(" ");
            count++;
        }
        return sb.toString();
    }

    //运算符优先级（数字越大优先级越高）
    public static int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;//非运算符
        }
    }

    public static void main(String[] args) {
        String infix = "1+((2+3)*4)-5";
        String s = infixToSuffix(infix);
        System.out.println(s + " len= " + s.length());
    }
}

不要有多余的空格：

我们可以完善之前的通过输入中缀表达式，转为后缀然后运算。

//给定后缀表达式
//        String str = "3 40 +";
        String infix = "1+((2+3)*4)-5";
        String suffix = 中缀转后缀.infixToSuffix(infix);
        //把后缀表达式存入List
        List<String> list = getList(suffix);
        int cal = cal(list);
        System.out.println("中缀表达式："+ infix);
        System.out.println("后缀表达式；" + suffix);
        System.out.println("运算结果为：" + cal);

欢迎访问我的个人博客学习交流：http://www.ayjup.cn