题解 | #表达式求值#

import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		while (in.hasNextLine()) {
			String str = in.nextLine();
			StringBuffer sbf = new StringBuffer(str);
			char[] cs = str.toCharArray();
			
			int flag = 0;
			while (flag >= 0) {
				int start = 0;
				int end = cs.length;
				for (int i = 0; i < cs.length; i++) {
					if (cs[i] == '(') {
						start = i;
						flag++;
					}
				}
				for (int i = 0; i < cs.length; i++) {
					if (cs[i] == ')' && i > start) {
						end = i;
						break;
					}
				}
//				System.out.println("start = " + start + "end = " + end);
				StringBuilder sbu = new StringBuilder();
				
				// 将'('与')'中间的值提取出来计算
				if (flag > 0) {
					for (int i = start+1; i < end; i++) {
						sbu.append(cs[i]);
					}
					flag -= 2;
				} else if (flag == 0) {
					flag -= 1;
					for (int i = 0; i < cs.length; i++) {
						sbu.append(cs[i]);
					}
					break;
				}
//				System.out.println("exp : " + sbu.toString());
				
				String res = compute(sbu.toString());
				//将计算结果字符串替换本来的字符串
				sbf.replace(start, end+1, res);
				cs = sbf.toString().toCharArray();
//				System.out.println(flag);
				// 继续循环
			}
			String result = compute(sbf.toString());
			System.out.println(result);
		}
		in.close();
	}
	
	// 按照优先级计算算术式
	// 此算术式为最简单的+、-、*、/运算式
	static String compute(String exp) {
//		System.out.println("exp:" + exp);
		Stack<Character> cStack = new Stack<>();
		Stack<Integer> numStack = new Stack<>();
		StringBuilder sbu = new StringBuilder();
		
		int result = 0;
		char[] cs = exp.toCharArray();
		
		for (char c : cs) {
			if (c == '*' || c == '/' || c == '+' || c == '-') {
				if (!sbu.toString().equals("")) {
					int num = Integer.parseInt(sbu.toString());
					numStack.push(num);
//					System.out.println("pushed num = " + num);
					
					if (!cStack.isEmpty()) {
						char com = cStack.pop();
//						System.out.println("got compute :" + com);
						if (com == '*') {
							int num2 = numStack.pop();
							int num1 = numStack.pop();
//							System.out.println("num1 :" + num1);
//							System.out.println("num2 :" + num2);
							
							numStack.push(num1 * num2);
//							System.out.println("pushed * num = " + num1 * num2);
						} else if (com == '/') {
							int num2 = numStack.pop();
							int num1 = numStack.pop();
//							System.out.println("num1 :" + num1);
//							System.out.println("num2 :" + num2);
							
							numStack.push(num1 / num2);
//							System.out.println("pushed / num = " + num1 / num2);
						} else if (com == '-') {
							int num2 = numStack.pop();
//							System.out.println("num2 :" + num2);
							
							numStack.push(0 - num2);
							// TODO
							if (cStack.size() == numStack.size() - 1 || cStack.size() == numStack.size() - 2) {
							} else {
								cStack.push(com);
//								System.out.println("pushed - num = " + (0 - num2));
							}
						} else {
							cStack.push(com);
//							System.out.println("Repushed compute : " + com);
						}
					}
					sbu = new StringBuilder();
				}
				cStack.push(c);
//				System.out.println("pushed compute : " + c);
			} else {
				sbu.append(c);
			}
		}
		int num = Integer.parseInt(sbu.toString());
		numStack.push(num);
//		System.out.println("pushed num == " + num);
		if (!cStack.isEmpty()) {
			char com = cStack.pop();
//			System.out.println("got compute :" + com);
			if (com == '*') {
				int num2 = numStack.pop();
				int num1 = numStack.pop();
				
				numStack.push(num1 * num2);
//				System.out.println("pushed * num = " + num1 * num2);
			} else if (com == '/') {
				int num2 = numStack.pop();
				int num1 = numStack.pop();
				
				numStack.push(num1 / num2);
//				System.out.println("pushed / num = " + num1 / num2);
			} else if (com == '-') {
				int num2 = numStack.pop();
				
				numStack.push(0 - num2);
//				System.out.println("pushed - num = " + (0 - num2));
				
//				System.out.println(cStack.size());
//				System.out.println(numStack.size());
				// TODO
				if (cStack.size() == numStack.size() - 1 || cStack.size() == numStack.size() - 2) {
				} else {
					cStack.push(com);
//					System.out.println("Repushed comoute = " + com);
				}
			} else {
				cStack.push(com);
//				System.out.println("Repushed compute : " + com);
			}
		}
		
		while ((!cStack.isEmpty()) || (numStack.size() >= 2)) {
			if (numStack.size() == 1) {
				break;
			}
			int num2 = numStack.pop();
//			System.out.println("num2 :" + num2);
			int num1 = numStack.pop();
//			System.out.println("num1 :" + num1);
			char c = '+';
			
			if (cStack.isEmpty()) {
			} else {
				c = cStack.pop();
//				System.out.println("compute:" + c);
			}
			if (c == '+') {
				numStack.push(num1 + num2);
//				System.out.println("+" + (num1 + num2));
			} else if (c == '-') {
				numStack.push(num1 + num2);
//				System.out.println("-" + (num1 + num2));
			} else if (c == '*') {
				numStack.push(num1 * num2);
//				System.out.println("*" + (num1 * num2));
//				System.out.println("size = " + numStack.size());
			} else if (c == '/') {
				numStack.push(num1 / num2);
//				System.out.println("/" + (num1 / num2));
			} 
		}
		
		result = numStack.pop();
//		System.out.println("result:" + result);
		return String.valueOf(result);
	}
}

我的基本思路（仅供参考）：首先计算括号里面的表达式，每次分离出来括号内的内容单独计算，这样每次计算就仅仅是加减乘除的运算了；再其次，当括号内的内容计算完成后，将原有的表达式的括号部分替换成计算出来的值，直至所有括号内容全部被替换；因为不用考虑表达式是否合法的问题（括号匹配），那么将最后的表达式进行计算则可以得出结果。

需要注意：①判定括号的逻辑：是最后一个左括号和左括号后的第一个右括号，这里需要判定的是右括号的下标是否大于左括号，在代码25行处；②加减乘除运算优先级：乘除运算优先级要大于加减运算，我在此处给出的解决办法是：当遇到下一个运算符时，需要判定上一个运算符是否为'*'、'/'运算，如果是，则需要先进行'*'、'/'运算，将两个运算数取出做运算然后将结果放入栈，再遇到下一个运算符的时候，再判定当前的运算符是否为'*'or'/'，这样最后最多只剩下一个'*'or'/'运算，更好计算；③减法运算会得出负数：减法运算时，需要特殊处理，其一是因为结果可能为负数，其二是因为可能是两个负数相减，这里我的处理方法是，判定当前符号是否为'-'，若是'-'，那么我将'-x'一起存入栈（代码143行），在最后做减法操作时（代码178行），和前一个数相加，这样处理起来相较于直接运算更为便捷，不用再考虑复杂情况；④入栈出栈逻辑：如果没有遇到运算符，则在原来的字符串（若存在）后append该字符，当且仅当上一个运算数结束了才会遇到运算符时，则此时将存有数值的字符串转换成Integer类型并存入数值栈（numStack），若运算符栈（cStack）非空，则按照第②步运算逻辑根据在栈中的运算符（上一个运算符）运算。

上述代码可简化，分离括号逻辑可以重新在另一个函数中完成，主函数仅仅完成传输表达式和得出结论的操作即可。总之，代码很丑陋，思路很大众，大家做个参考，有更好的想法欢迎评论。