【困难】公式字符串求值－Java

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.String; import java.util.Deque; import java.util.LinkedList; /** * 公式字符串求值 * * 【题目】 * 给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号，返回公式的计算结果。 * * 【说明】 * 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。 * 2.如果是负数，就需要用括号括起来，比如"4*(-3)"。但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如 * "-3*4"和"(-3*4)"都是合法的。 * 3.不用考虑计算过程中会发生溢出的情况。 * * 【难度】 * 困难 * * 【解答】 * 本题考查面试者设计程序和代码实现的能力，实现方式有很多，本文提供一种方法供读者参考。假设value方法是一个递归过程，具体 * 解释如下。 * * 从左到右遍历str，开始遍历或者遇到字符'('时，就进行递归过程。当发现str遍历完，或者過到字符')'时，递归过程就结束。比如 * "3*(4+5)+7"，一开始遍历就进入递归过程value(str,0)，在递归过程value(str,0)中继续遍历str，当遇到字符'('时，递归 * 过程value(str,0)又重复调用递归过程value(str,3)。然后在递归过程value(str,3)中继续遍历str，当遇到字符')'时，递 * 归过程value(str,3)结束，并向递归过程value(str,0)返回两个结果，第一结果是value(str,3)遍历过的公式字符子串的结果， * 即"4+5"==9，第二个结果是value(str,3)遍历到的位置，即字符")"的位置==6。递归过程value(str,0)收到这两个结果后，既 * 可知道交给value(str,3)过程处理的宇符串结果是多少("(4+5)"的结果是9)，又可知道自己下一步该从什么位置继续遍历(该从位 * 置6的下一个位置(即位置7)继续遍历)。总之，value方法的第二个参数代表递归过程是从什么位置开始的，返回的结果是一个长度为 * 2的数组，记为res。res[O]表示这个递归过程计算的结果，res[1]表示这个递归过程遍历到str的什么位置。 * * 既然在递归过程中遇到'('就交给下一层的递归过程处理，自己只用接收'('和')'之间的公式字符子串的结果，所以对所有的递归过 * 程来说，可以看作计算的公式都是不含有'('和')'字符的。比如，对递归过程value(str,0)来说，实际上计算的公式是"3*9+7"， * "(4+5)"的部分交给递归过程value(str,3)处理，拿到结果9之后，再从字符'+'继续。所以，只要想清楚如何计算一个不含有'(' * 和')'的公式字符串，整个实现就完成了。 * * 全部过程请参看如下代码中的getValue方法。 * * @author Created by LiveEveryDay */ public class FormulaStringEvaluation { public static int getValue(String exp) { return value(exp.toCharArray(), 0)[0]; } private static int[] value(char[] chars, int i) { Deque<String> deq = new LinkedList<>(); int pre = 0; int[] bra = null; while (i < chars.length && chars[i] != ')') { if (chars[i] >= '0' && chars[i] <= '9') { pre = pre * 10 + chars[i++] - '0'; } else if (chars[i] != '(') { addNum(deq, pre); deq.addLast(String.valueOf(chars[i++])); pre = 0; } else { bra = value(chars, i + 1); pre = bra[0]; i = bra[1] + 1; } } addNum(deq, pre); return new int[]{getNum(deq), i}; } private static void addNum(Deque<String> deq, int num) { if (!deq.isEmpty()) { int cur = 0; String top = deq.pollLast(); if (top.equals("+") || top.equals("-")) { deq.addLast(top); } else { cur = Integer.parseInt(deq.pollLast()); num = top.equals("*") ? (cur * num) : (cur / num); } } deq.addLast(String.valueOf(num)); } private static int getNum(Deque<String> deq) { int res = 0; boolean add = true; String cur = null; int num = 0; while (!deq.isEmpty()) { cur = deq.pollFirst(); if (cur.equals("+")) { add = true; } else if (cur.equals("-")) { add = false; } else { num = Integer.parseInt(cur); res += add ? num : (-num); } } return res; } public static void main(String[] args) { String exp = "48*((70-65)-43)+8*1"; System.out.printf("The evaluation result is: %d", getValue(exp)); } } // ------ Output ------ /* The evaluation result is: -1816 */