表达式求值
# 📃 题目描述
题目链接:BM49 表达式求值 (opens new window)
# 🔔 解题思路
import java.util.*;
public class Solution {
public int solve (String s) {
// write code here
char[] chars = s.toCharArray();
Stack<Integer> stack = new Stack<>();
int num = 0;
// op 表示 num 前的符号
char op = '+';
for (int i = 0; i < chars.length; i ++) {
char c = chars[i];
// 整数可能不止一位
if (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
}
// '('
else if (c == '(') {
// 找到对应的 ),里面可能嵌套很多个 ()
int j = i + 1;
// ( 的数量
int count = 1;
while (count > 0 && j < chars.length) {
if (chars[j] == '(') {
count ++;
}
if (chars[j] == ')') {
count --;
}
j ++;
}
// 递归求 () 内的表达式
num = solve(s.substring(i + 1, j - 1));
i = j - 1;
}
// op
if (!Character.isDigit(c) || i == chars.length - 1) {
// 处理上一个运算符
if (op == '+') {
stack.push(num);
} else if (op == '-') {
stack.push(-num);
} else if (op == '*') {
stack.push(num * stack.pop());
} else if (op == '/') {
stack.push(stack.pop() / num);
}
// 更新当前运算符
op = c;
num = 0;
}
}
int res = 0;
while (!stack.isEmpty()) {
res += stack.pop();
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10