题解 | #表达式求值#
表达式求值
https://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d
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）非空，则按照第②步运算逻辑根据在栈中的运算符（上一个运算符）运算。
上述代码可简化，分离括号逻辑可以重新在另一个函数中完成，主函数仅仅完成传输表达式和得出结论的操作即可。总之，代码很丑陋，思路很大众，大家做个参考，有更好的想法欢迎评论。
腾讯成长空间 449人发布
