题解 | #表达式求值#, 重点在思路
解题思路
两个Stack实现:stack和addStack。addStack专门进行加减法。以表达式10*20-100*(88-76*2+(200-2))为例整体思路为,把表达式按10,*,20,-,100,*,(,88,-,76,*,2,+,(,200,-,2,),)的顺序,逐个压入栈中stack。
情况1:在压栈过程中,如果栈顶元素为*或者/、且当前待压入的元素为数字。譬如栈中元素为10,*,待压入数据为20。则进行乘除运算。针对可能存在特殊情况譬如(10+20)*30,在压栈过程中括号内的内容会在压入‘)’的时候计算完毕,然后压栈,变为30*30。
情况2:在压栈过程中,只要遇到‘)’字符会强制对当前括号的内容进行运算,比如例子表达式运行到(200-2)的‘)’时候,会新建一个加减法栈addStack,在stack以2,-,200的顺序出栈的时候,addStack以相同的顺序压入栈中,这样在addStack出栈的过程中可以,以从左往右的方式执行200-2的运算。针对情况2有人会说括号内只会存在加减法吗?是的,在情况1中,乘除法已经换算完毕。还有人会说括号内还有括号怎么办?按示例压栈,第一个‘)’就是最内层的括号。
情况3:如果只输入了一串数字,比如4000,需要特殊处理,因为字符串遍历完了就完了。这时还没有把数字压入栈中:if (!prefix.equals("")) { stack.push(Integer.valueOf(prefix)); }
情况4:如果以负数开头,或者计算过程压入负数怎么办?开头为负号的,把负号去掉,给数字取反符合。其它情况只有在‘(’符号之后才有可能插入负号,其它情况要么语法错误,要么是做减法,这里也是取反后把前面的负号去掉。
处理难点:把字符串精准的分割为数字或者操作符,数字是每次都要压入栈中,或者计算后压入栈中。操作符除了‘)’,其余无脑压入栈中,当遇到第一个‘)’会触发计算括号内内容。
最后想要说的是,重点在思路,细节可以慢慢完善。
这应该不算简单题吧,考虑的情况太多,太麻烦~~
public class Test { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextLine()) { // 注意 while 处理多个 case String format = in.nextLine(); String prefix = ""; Stack<Object> stack = new Stack<>(); for (int i = 0; i < format.length(); i++) { char c = format.charAt(i); if (c != '+' && c != '-' && c != '*' && c != '/' && c != '(' && c != ')') { prefix += c; } else { //如果上一个数据为数字 if (!prefix.equals("")) { Integer cur = Integer.parseInt(prefix); //计算数字是否为负号 cur = calculateCurSysbol(stack, cur); if (!stack.isEmpty()) { //栈不为空,优先进行乘除法运算 doMultiplicationAndDivision(stack, cur); } else { //栈为空,压入数据 stack.push(cur); } //数字逻辑处理压栈后,清空 prefix = ""; } //如果上一个数据为操作符 if (c == ')') { //计算出括号内的所有值 //再新建一个栈addStack,把括号内的内容pop后压入addStack Stack<Object> addStack = new Stack<>(); while (!(stack.peek() instanceof Character && (Character) stack.peek() == '(')) { addStack.push(stack.pop()); } stack.pop(); //从左往右执行加减法,默认栈是从右往左 doReverse(addStack); //括号计算出来的数据,优先进行乘除法,否则,压入栈中 doMultiplicationAndDivision(stack, (Integer) addStack.pop()); } else { //只要不是)字符结尾,统统压入栈中 stack.push(c); } } } //针对只有一个数字,或者数字结尾 if (!prefix.equals("")) { stack.push(Integer.valueOf(prefix)); } //构建加减法栈 Stack<Object> addStack = new Stack<>(); while (!stack.isEmpty()) { addStack.push(stack.pop()); } //执行加减法 doReverse(addStack); System.out.println(addStack.peek()); } } //处理负号数字 //开头为负号 //负号前不是数字,是操作符(的 //符合以上两种情况的数字加负号,弹出多余负号 private static Integer calculateCurSysbol(Stack<Object> stack, Integer cur) { if (stack.size() == 1 && (Character) stack.peek() == '-') { stack.pop(); cur = -cur; } if (stack.size() > 1 && (Character) stack.peek() == '-') { Object pop = stack.pop(); Object pre2 = stack.peek(); if (pre2 instanceof Character && (Character) pre2 == '(') { cur = -cur; } else { stack.push(pop); } } return cur; } private static void doReverse(Stack<Object> addStack) { while (addStack.size() != 1) { Integer last = (Integer) addStack.pop(); Character flOperation = (Character) addStack.pop(); Integer first = (Integer) addStack.pop(); Integer partResult = doOperation(last, first, flOperation); addStack.push(partResult); } } //放乘除积,或者本身 private static void doMultiplicationAndDivision(Stack<Object> stack, Integer cur) { if (!stack.isEmpty()) { Object peek = stack.peek(); //栈顶是*/,cur是数字 if (peek instanceof Character && ((Character) peek == '*' || (Character) peek == '/')) { Character operation = (Character) stack.pop(); Integer pre = (Integer) stack.pop(); Integer result = doOperation(Integer.valueOf(pre), cur, operation); stack.push(result); } else { stack.push(cur); } } else { stack.push(cur); } } //执行简单的加减法 private static Integer doOperation(Integer pre, Integer cur, Character charr) { if (charr == '+') { return pre + cur; } else if (charr == '-') { return pre - cur; } else { throw new RuntimeException(); } }