Java教程

栈的应用之中缀计算器

本文主要是介绍栈的应用之中缀计算器,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、中缀表达式

1.是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4)

2.与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。

3.与前缀或后缀记法不同的是,中缀记法中括号是必需的。

二、格式化表达式

如果原封不动的遍历表达式字符串(10+20/2*3)/2+8

将得到如下结果:

[(, 1, 0, +, 2, 0, /, 2, *, 3, ), /, 2, +, 8]

最好的分隔结果是:[(, 10, +, 20, /, 2, *, 3, ), /, 2, +, 8]

思路:将字符串格式化为如下情形,再进行分隔即可

#(#10#+#20#/#2#*#3#)#/#2#+#8

三、栈实现中缀表达式

创建两个栈  :operatorStack(操作符栈)     和        numberStack(数字栈)

四、代码实现

package p2.线性结构;


public class InfixCalculator {
    public static void main(String[] args) {
        String expression = "(10+20/2*3)/2+8";
        try {
            int result = evaluateExpression(expression);
            System.out.println(result);
        }catch(Exception e){
            e.printStackTrace();
            System.out.println("Wrong expression:"+expression);
        }

    }


    private static int evaluateExpression(String expression) {
        //需要两个辅助栈
        ArrayStack<Character> operatorStack = new ArrayStack<>();
        ArrayStack<Integer> numberStack = new ArrayStack<>();

        //格式化表达式
        expression = insertBlanks(expression);
        String[] tokens = expression.split(" ");//字符串用空格切割
        for (String token : tokens) {//token===tokens[i]
            //过滤空串,切割出来的字符有的是空串(有字符串无内容,即长度是0) 空串不是null,null为空 啥都没有
            if (token.length() == 0) {
                continue;

                //遍历到 + - 号

            } else if (token.equals("+") || token.equals("-")) {//token是字符串,拿equals来比较的  operatorStack是存字符的栈,里面元素都是字符,是拿字符进行比较
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-' || operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    //如果之前是别的 + - * / 需要弹栈并计算
                    processAnOperator(numberStack, operatorStack);//可能需要进行几次,所以是while 循环,一直到栈弹空了或者不是其他加减乘除再进栈  如开始栈里有+ *,要进来+,需要两次
                }
                //如果操作符栈为空 或者 不为空 但栈为(
                operatorStack.push(token.charAt(0));// operatorStack是存字符的,token是字符串,放不进去的,要把字符放进去

                //遍历到 * / 号
            } else if (token.equals("*") || token.equals("/")) {
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    //如果之前是别的 * / 需要弹栈并计算
                    processAnOperator(numberStack, operatorStack);
                }
                //如果操作符栈为空 或者 不为空 但栈为(
                operatorStack.push(token.charAt(0));

                //遍历到(
            } else if (token.equals("(")) {
                operatorStack.push(token.charAt(0));
            } else if (token.equals(")")) {
                //只要操作符栈的栈顶不是左括号( 就挨个弹栈计算即可
                while (operatorStack.peek() != '(') {
                    processAnOperator(numberStack, operatorStack);
                }
                //最后清掉左括号
                operatorStack.pop();

                //遍历到数字
            } else {
                //numberStack.push(Integer.parseInt(token));  把数字字符串解析成一个数字       通过Integer的静态方法 或 new Integer
                numberStack.push(new Integer(token));//根据一个数字字符串去创建一个Integer对象
            }
        }
        //处理最后面的操作符
        while (!operatorStack.isEmpty()) {
            processAnOperator(numberStack, operatorStack);
        }
        return numberStack.pop();//计算的最后结果肯定在数字栈里面,把这个元素弹栈即可
    }

    //操作符栈弹栈一个元素,数字栈弹栈两个数字 并将新的结果进栈到数字栈
    private static void processAnOperator(ArrayStack<Integer> numberStack, ArrayStack<Character> operatorStack) {
        char op=operatorStack.pop();
        int num1=numberStack.pop();
        int num2=numberStack.pop();
        //num2 op num1    数字先弹出来的放操作符右边,后弹出来的放操作符左边,操作符只弹一个,放中间
        if(op=='+'){
            numberStack.push(num2+num1);
        }else if(op=='-'){
            numberStack.push(num2-num1);
        }else if (op=='*'){
            numberStack.push(num2*num1);
        }else{
            numberStack.push(num2/num1);
        }
    }

    //对原表达式进行格式化,给所有的非数字字符两边添加空格
    private static String insertBlanks(String expression) {

/*
        “(10+20/2*3)/2+8”
         “ ( 10 + 20 / 2 * 3 )  / 2 + 8”  字符串跟数组一样,一个字符串一旦创建出来,其内容 长度不能改变,我们不可能在原字符串上进行增、删、改  (可查)所以需遍历出一个新字符串
        */

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);//先从左到右把字符取出来,往c这个字符里面放
            if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') {
                sb.append(' ');
                sb.append(c);
                sb.append(' ');
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}


 

这篇关于栈的应用之中缀计算器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!