表达式求值的递归与非递归java实现

【问题描述】 给定字符串str,str表示一个数学公式,里面含有运算符加减乘除、数字以及左右括号,返回公式的计算结果,如str="-1+2+3-4*(12-10)",返回-4。

一、递归求解

假设makevalue方法是一个递归求值过程,str="1+2*(3+4)-5"递归求值过程描述如下:

1.从字符串下标0位置开始遍历,如果遍历到’(‘则进入下一层递归;如果遍历到’)'或str遍历完,当前递归调用结束,并向上一递归调用过程返回递归调用结果——遍历结束位置和当前子串计算结果

2.如果遍历到运算符,直接从双端队列deque队尾入队

3.如果遍历到数字num,首先deque尾部元素opr出队,然后判断opr的运算符类型:若opr为’+‘或’-’,则num直接从队尾入队;若opr为’*‘或’/’,为保证其运算优先级,队尾元素pre出队,然后进行num=pre·opr·num运算,最后将运算结果num从队尾入队

递归过程说明:

刚开始进行遍历就进入递归调用makevalue(str,0),当遇到字符’(‘时,从makevalue(str,0)进入递归调用makevalue(str,4),当遇到’)'字符时,makevalue(str,4)递归调用结束,并向makevalue(str,0)返回两个递归调用结果:①makevalue(str,0)遍历结束位置8 ②当前字串的计算结果即"3+4"=7

用数组a[]=new int[2]来保存这两个结果,a[0]=8,用来告知上层调用其下一遍历位置应该从哪儿开始,a[1]=7,存储子串计算结果。对于makevalue(str,0),a[0]保存的是整个字符串str计算结果,a[1]保存的是整个字符串str的长度

子串计算结果说明:

因为每次遇到’(‘就进入下层递归调用,括号()中的子串结果是交给下层函数计算的,上层只需要接受下层返回的计算结果,所以对所有递归过程来说,都是不含字符’(‘和’)’,如对makevalue(str,0)来说,计算的实际上是1+2*7-5,因为(3+4)是交给下层makevalue(str,4)计算完成的,自己只需要接受下层返回的结果7

通过2、3步描述和以上说明,不难可以看出双端队列deque实际上保存的就是当前递归过程不包含字符’(‘和’)’,也不包含字符’*‘和’/’(见3)的字符串,只包含操作符‘+’、‘-’和操作数,即对makevalue(str,0)来说,deque={“1”,"+",“14”,"-",“5”},对makevalue(str,4)来说,deque={“3”,"+",“4”}

【算法描述】

    public static int[] makeValue(char[] chas, int i) {
        int val = 0;
        int[] a = new int[2];
        Deque<String> deque = new LinkedList<String>();
        while (i < chas.length && chas[i] != ')') {
            if (chas[i] >= '0' && chas[i] <= '9')
                val = val * 10 + chas[i++] - '0';
            else if (chas[i] != '(') {   //chas[i] in {+-*/}
                addNum(deque, val);
                deque.addLast(String.valueOf(chas[i++]));
                val = 0;
            } else {
                a = makeValue(chas, i + 1);
                val = a[0];
                i = a[1] + 1;
            }
        }
        addNum(deque, val);
        return new int[]{popNum(deque), i};
    }

    public static void addNum(Deque<String> deque, int num) {
        if (!deque.isEmpty()) {
            String str = deque.pollLast();
            switch (str) {//保证乘除优先
                case "+":
                case "-":
                    deque.addLast(str);
                    break;
                case "*":
                case "/":
                    int val = Integer.valueOf(deque.pollLast());
                    num = str.equals("*") ? (val * num) : (val / num);
            }
        }
        deque.addLast(String.valueOf(num));
    }

    public static int popNum(Deque<String> deque) {
        String val = "";
        boolean isPlus = true;
        int num = 0;
        while (!deque.isEmpty()) {
            val = deque.pollFirst();
            if (val.equals("+"))
                isPlus = true;
            else if (val.equals("-"))
                isPlus = false;
            else num += isPlus ? Integer.valueOf(val) : -Integer.valueOf(val);
        }
        return num;
    }
    public static void main(String[] args) {
        System.out.println("-1+2+3-4*(12-10)=" + 
        makeValue("-1+2+3-4*(12-10)".toCharArray(), 0)[0]);
    }

表达式求值的递归与非递归java实现
二、非递归求解

采用Dijkstra的双栈算术表达式求值算法,栈st2用于保存运算符,st1用于保存操作数,非递归求值过程描述如下:

用字符’#'对str进行界定str="#str#",并假设操作数位数只有一位

1.初始化操作数栈st1与运算符st2,str[0]即’#'压入栈st2

2.遍历str[1…str.length-1],读入第一个字符ch,循环执行以下操作:
2.1.如果ch是数字,将其压入操作数栈,读取下一字符ch
2.2.如果ch是运算符,则需要与st2栈顶元素进行优先级比较:
……若ch优先级大,则ch压入st2栈,读入下一字符ch
……若ch优先级小,则弹出st2栈顶的运算符,从st1栈弹出两个操作数,进行相应运算,结果压入st1栈
……若优先级相等,则st2.top()==’(‘且ch==’)’,弹出st2栈顶的’(’,相当于括号匹配成功,然后读入下一字符ch

在处理完最后一个右括号之后,st1上只会有一个值,即为所求表达式的值

非递归求解过程比较容易理解,主要就是算符间优先关系的判定,以及如何根据优先级关系的不同采取不同的决策

算符间优先关系:

算术四则运算规则:
(1)先乘除,后加减;
(2)从左算到右;
(3)先括号内,后括号外。

将界定符#与运算符统称为算符,根据算术运算规则,不难得到如下算符间优先关系表,θ1<θ2表示θ1的优先权低于θ2。表达式求值的递归与非递归java实现
由规则(1),先进行乘除运算,后进行加减运算,所以有’+’<’*’,’+’<’/’;’*’>’+’;’/’>’+’
由规则(2),运算遵循左结合性,当两个运算符相同时,先出现的运算符优先级高,所以有’+’>’+’;‘−’>‘−’;’*’>’*’;’/’>’/’
由规则(3),括号内的优先级高,+、−、*和/为θ1时的优先性均低于’(‘但高于’)’

算符优先表

通过将算符映射成ASCII码,用二维数组下标来表示。查ASCII表,可知算符的字符编码值在35-47之间,所以可以通过构造一个50×50的二维数组priorityTab,来存储算符间的优先关系,priorityTab[‘+’][‘+’]=‘>’,表示θ1=’+’>θ2=’+’,这样可以省去在遍历过程中太多的if判定语句
表达式求值的递归与非递归java实现
【算符优先表构造过程】

    public static char[][] getPriorityTab() {
        char[] chas = "+-*/()#".toCharArray();
        char[][] priority = new char[50][50];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < chas.length; j++) {
                priority[chas[j]][chas[i]] = '>';
            }
        }
        for (int i = 2; i < 5; i++) {
            for (int j = 0; j < chas.length; j++) {
                priority[chas[j]][chas[i]] = '<';
            }
        }
        for (int i = 5; i < chas.length; i++) {
            for (int j = 0; j < chas.length; j++) {
                priority[chas[j]][chas[i]] = '>';
            }
        }
        for (int i = 0; i < chas.length; i++) {
            priority['('][chas[i]] = '<';
            priority[')'][chas[i]] = '>';
            priority['#'][chas[i]] = '<';
        }
        priority['*']['*'] = '>';
        priority['*']['/'] = '>';
        priority['/']['*'] = '>';
        priority['/']['/'] = '>';

        priority['('][')'] = '=';
        priority['#']['#'] = '=';

        priority[')']['('] = 0;
        priority['#'][')'] = 0;
        priority['(']['#'] = 0;
        return priority;
    }

测试一下~~

    char[][] priorityTab = getPriorityTab();
    char[] chas = "+-*/()#".toCharArray();
    for (int j = 0; j < 7; j++) {
        for (int k = 0; k < 7; k++) {
            System.out.print(priorityTab[chas[j]][chas[k]]);
        }
        System.out.println();
    }

没有错误呢~~
表达式求值的递归与非递归java实现
【算法描述】

    public static double makeValue(char[] chas) {
        int i = 1;
        char opt;
        double opn = 0, opnl, opnr;
        char[][] priorityTab = getPriorityTab();
        Stack<Double> st1 = new Stack<Double>();//num
        Stack<Character> st2 = new Stack<Character>();//opt

        st2.push('#');
        while (i<chas.length) {
            while (chas[i] >= '0' && chas[i] <= '9')
                opn = opn * 10 + chas[i++] - '0';

            if (opn!=0) {
                st1.push(opn);
                opn=0;
            }

            switch (priorityTab[st2.lastElement()][opt = chas[i]]) {
                case '<':
                    st2.push(opt);
                    i++;
                    break;
                case '>'://先pop出来的是右操作数,这错误我找了半天
                    opnr = st1.pop();
                    opnl = st1.pop();
                    st1.push(getOpn(opnl, st2.pop(), opnr));
                    break;
                case '=':
                    st2.pop();
                    i++;
                    break;
            }
        }
        return st1.lastElement();
    }
    public static double getOpn(double opnl, char opt, double opnr) {
        switch (opt) {
            case '+':
                return opnl + opnr;
            case '-':
                return opnl - opnr;
            case '*':
                return opnl * opnr;
            default:
                return opnl / opnr;
        }
    }

表达式求值的递归与非递归java实现
当然此算法还不能计算操作数为负数的情况,读者可以自行改进,本人编码水平有限,如有错误欢迎批评指正emmm

未分类
匿名

发表评论

匿名网友

    • 阿聪 阿聪 0

      Edge浏览器群,阿聪到此一游