AcWing 3302. 表达式求值
原题链接
简单
作者:
Y_57
,
2021-05-16 14:26:33
,
所有人可见
,
阅读 205
递归+栈(Java版)
题解
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
System.out.println(calc(new Scanner(System.in).nextLine()));
}
public static int calc(String str) {
char[] arr = str.toCharArray();
Stack<Integer> stack = new Stack<>();
int num = 0;
//默认符号为+
char sign = '+';
for (int i = 0; i < arr.length; i++) {
//随便给个初始值
char c = 0;
//将连续的数字字符转换为数字
while(i < arr.length && Character.isDigit(c = arr[i])) {
num = num * 10 + (c - '0');
i++;
}
//遇到左括号就将子式提取出来,并递归处理
if (c == '(') {
//左括号的个数
int cnt = 0;
int j = i;
for (; i < arr.length; i++) {
if (arr[i] == '(') cnt++;
if (arr[i] == ')') cnt--;
//左括号匹配完毕
if (cnt == 0) break;
}
//递归
num = calc(str.substring(j + 1, i + 1));
}
if (sign == '+') {
stack.push(num);
} else if (sign == '-') {
stack.push(-num);
} else if (sign == '*') {
//拿出前一个数来相乘
stack.push(stack.pop() * num);
} else if (sign == '/') {
//拿出前一个数来相除
stack.push(stack.pop() / num);
}
//sign用来记录上一符号
sign = c;
//恢复
num = 0;
}
int ans = 0;
//计算和
while (!stack.isEmpty()) {
ans += stack.pop();
}
return ans;
}
}