Leetcode224 -- 基本计算器及其拓展
题目分析:
其实这个计算器的实现并不难,因为除了括号就剩下加减法嘛,括号肯定比加减法先执行,但是加减法是同级的,只是会改变数字的正负号而已,所以实现的逻辑并不是很难,我们只需要一个栈,来保存当前的符号sign即可.
遇到 '(' 就将当前符号入栈
遇到 ')' 就将当前符号弹出
遇到 '+' 就获取栈顶的符号(注意不是弹出),因为+不改变方向,所以从栈中取出来什么就是什么
遇到 '-' 也获取栈顶的符号(注意不是弹出),但是 - 会改变方向,所以给取出来的符号取反即可
遇到数字 就一直向下计算,直到下一个符号不是数字
最后把每个阶段算出来的结果相加就是答案
代码实现:
class Solution {
public int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);//这个栈中保存的是 符号
int sign = 1; // 整数 -1 +1 代表当前的符号
int res = 0,i = 0, n = s.length();
while(i < n) {
char c = s.charAt(i);
switch(c) {
case ' ':{
i++;
break;
}
case '+':{
i++;
sign = stack.peek();
break;
}
case '-':{
i++;
sign = -stack.peek();
break;
}
case '(':{
i++;
stack.push(sign);
break;
}
case ')':{
i++;
stack.pop();
break;
}
default:{
long sum = 0;
while(i < n && Character.isDigit(s.charAt(i))) {
sum = sum * 10 + s.charAt(i) - '0';
i++;
}
res += sum * sign;
}
}
}
return res;
}
}
题目拓展:
这个拓展是来自于Ks的一道面试题,也没有明确说明,但默认能猜出来是考什么
区别及实现思路:
先说一下和Leetcode224的区别,就是多了*/这两个符号,并且*/个加减不属于一个级别,*/优先于+-,所以这里扯到了优先级的概念,并且还有(),为了保证括号内的表达式先被计算,我们定义( 的优先级是最低的,这样定义了优先级之后,就很清晰了
实现思路如下:
1.遇到数字直接加到操作数列表
2.遇到优先级,与最近加入的优先级做对比,
2.1 如果大于最近的优先级,则将操作符直接加入到操作符列表,
2.2 否则从操作列表里拿一个操作符和两个操作数进行计算,将计算的结果加到原来的列表
重复上面的操作直到找到一个比当前操作符优先级更低的操作符(在列表中)或者列表为空,再将当前的操作符加入到列表。
由于括号的优先级最高,我们要让括号里面的操作符最先被计算,所以可以将'('的优先级设为最低
代码实现:
public double calculateKs(String expression) {
Deque<Double> numbers = new LinkedList<>();
Deque<Character> operators = new LinkedList<>();
int index = 0,len = expression.length();
while(index < len) {
char c = expression.charAt(index);
if(c == '(') {
operators.push(c);
index++;
}else if(c == ')') {
//计算括号内的表达式
while(operators.peek() != '(') {
//单点操作,不是连点操作,所以得循环一直算,直到不符合条件为止
compute(numbers,operators);
}
operators.pop();
index++;
}else if(isOperator(c)) {
//处理操作符,考虑优先级
while(!operators.isEmpty() && precedence(operators.peek()) >= precedence(c)) {
//单点操作,不是连点操作,所以得循环一直算,直到不符合条件为止
compute(numbers,operators);
}
operators.push(c);
index++;
}else if(Character.isDigit(c)) {
//解析数字 -- 因为可能不只是一位数,所以要进行拼接
StringBuilder sb = new StringBuilder();
while(index < len && Character.isDigit(expression.charAt(index))) {
sb.append(expression.charAt(index++));
}
numbers.push(Double.parseDouble(sb.toString()));
}
}
//计算剩余的操作
while(!operators.isEmpty()) {
//单点操作,不是连点操作,所以得循环一直算
compute(numbers,operators);
}
return numbers.pop();
}
public boolean isOperator(char c) {
return c =='+' || c == '-' || c == '*' || c == '/';
}
//定义操作符的优先级
public int precedence(char c) {
if(c == '+' || c == '-') {
return 1;
}else if(c == '*' || c == '/') {
return 2;
}
return 0;
}
//单点操作,不是连点操作,所以就算一次
public void compute(Deque<Double> numbers,Deque<Character> operators) {
if(numbers.size() < 2) {
return;
}
double b = numbers.pop();
double a = numbers.pop();
char operator = operators.pop();
double res = 0.0;
switch(operator) {
case '+':{
res = a + b;
break;
}
case '-':{
res = a - b;
break;
}
case '*':{
res = a * b;
break;
}
case '/':{
res = a / b;
break;
}
default:
break;
}
numbers. Push(res);
}