题解 | #四则运算#
四则运算
https://www.nowcoder.com/practice/9999764a61484d819056f807d2a91f1e?tpId=37&tqId=21273&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D3%26judgeStatus%3D1%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=3&judgeStatus=1&tags=&title=
- 将一个表达式分成三部分，数字、运算符和括号部分，将括号里的表达式看做一个整体，又可以分成这样三部分，于是可以用递归解决。
- 遇到数字就存到栈里；遇到加减运算符接下来还是存到栈里，遇到乘除运算符就取出栈顶运算完再放进栈里；遇到括号就用递归解决括号里的表达式。
- 定义了一个运算符的自由度，代表该运算符前的括号是否是完整的，比如示例3+2*{1+2*[-4/(8-6)+7]}这样一个表达式中，第一个+号和第一个*号是0自由度的，其他不为0；但如果只看大括号{}里的部分即1+2*[-4/(8-6)+7]，此时1后面的+号、2后面的*号变成了0自由度，这在递归中可以解决。
- 将原始表达式存到一个作为成员变量的字符数组，这样递归时只需要传递首尾两个参数，不需要频繁的截取数组或字符串。
- 计算时用的double类型，最后输出时如果小数部分为0就取整输出。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
Solution sl = new Solution();
double num = sl.getAnswer(input);
if (Math.round(num) - num == 0) {
System.out.println((int) num);
} else {
System.out.println(num);
}
}
}
class Solution {
char[] chars;
char[] brackets = {')', ']', '}'};
char[] operators = {'+', '-', '*', '/'};
//将表达式转换为字符数组成员变量，计算局部表达式时只需要传递两个下标
public double getAnswer(String expression) {
chars = expression.toCharArray();
return calculate(0, chars.length);
}
public double calculate(int pos, int end) {
Stack<Double> store = new Stack<>();
while (pos < end) {
char cur = chars[pos];
double val = 0;
if (cur == '(' || cur == '[' || cur == '{') {
int target = findFreeTarget(chars, pos + 1, end, 1, brackets);
val = calculate(pos + 1, target);
pos = target + 1;
} else if (Character.isDigit(cur)) {
while (pos < end && Character.isDigit(chars[pos])) {
val = val * 10 + chars[pos] - '0';
pos++;
}
} else {
//找到下一个自由度为0的运算符，计算这一段表达式的值
int target = findFreeTarget(chars, pos + 1, end, 0, operators);
switch (cur) {
case '+':
val = calculate(pos + 1, target);
break;
case '-':
val = -calculate(pos + 1, target);
break;
case '*':
val = store.pop() * calculate(pos + 1, target);
break;
default:
val = store.pop() / calculate(pos + 1, target);
}
pos = target;
}
store.push(val);
}
double answer = 0;
while (!store.isEmpty()) {
answer += store.pop();
}
return answer;
}
//找到下一个自由度为0的 + 号或 - 号, 定义自由度为该字符前左括号和右括号的个数
public int findFreeTarget(char[] chars, int pos, int end, int freedom, char[] targets) {
while (pos < end) {
char cur = chars[pos];
if (cur == '(' || cur == '[' || cur == '{') {
freedom++;
} else if (cur == ')' || cur == ']' || cur == '}') {
freedom--;
}
if (freedom == 0) {
for (char target : targets) {
if (cur == target) {
return pos;
}
}
}
pos++;
}
return end;
}
}