公式字符串求值
给定一个字符串str, str表示一个公式,公式里可能有整数、加减乘除符号和左右括号,返回公式的计算结果。
可以认为给定的字符串一定是正确的公式,即不需要对str做公式有效性检查。
如果是负数,就需要用括号括起来,比如”4*(-3)”。但如果负数作为公式的开头或括号部分的开头,则可以没有括号,比如”-3*4”和”(-3*4)”都是合法的。
不用考虑计算过程中会发生溢出的情况。

/*
* 1.从左到右遍历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[0]表示这个递归过程计算的结果,res[1]表示这个递归过程遍历到str的什么位置。
* 2.计算过程如下:
* a.先计算乘除法,剩下加减法再统一从左到右计算;
* b.遇到左括号,进入递归。遇到右括号跳出递归;
* c.注意代码中对输入字符串的数字字符的处理。
*/
public class 公式字符串求值 { public static int getValue(String str) { return value(str.toCharArray(), 0)[0]; } //递归函数 public static int[] value(char[] str, int i) { LinkedList que = new LinkedList(); int pre = 0; int[] bra = null; while (i < str.length && str[i] != ')') { if (str[i] >= '0' && str[i] <= '9') { pre = pre * 10 + str[i++] - '0'; } else if (str[i] != '(') { addNum(que, pre); que.addLast(String.valueOf(str[i++])); pre = 0; } else { //递归操作 bra = value(str, i + 1); pre = bra[0]; //递归过程中计算的结果 i = bra[1] + 1; //递归过程遍历到str的什么位置 } } addNum(que, pre); return new int[] { getNum(que), i }; } //计算两个数的加法 public static void addNum(LinkedList que, int num) { if (!que.isEmpty()) { int cur = 0; String top = que.pollLast(); if (top.equals("+") || top.equals("-")) { que.addLast(top); } else { //字符串转换成整数(计算乘除) cur = Integer.valueOf(que.pollLast()); num = top.equals("*") ? (cur * num) : (cur / num); } } que.addLast(String.valueOf(num)); } //获取加减计算的数值 public static int getNum(LinkedList que) { int res = 0; boolean add = true; String cur = null; int num = 0; while (!que.isEmpty()) { cur = que.pollFirst(); if (cur.equals("+")) { add = true; } else if (cur.equals("-")) { add = false; } else { num = Integer.valueOf(cur); res += add ? num : (-num); } } return res; } public static void main(String[] args) { String exp = "48*((70-65)-43)+8*1"; System.out.println(getValue(exp)); exp = "4*(6+78)+53-9/2+45*8"; System.out.println(getValue(exp)); exp = "10-5*3"; System.out.println(getValue(exp)); exp = "-3*4"; System.out.println(getValue(exp)); exp = "3+1*4"; System.out.println(getValue(exp)); } }