题目
给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外),计算其结果。
表达式仅包含非负整数、+、-、*、/四种运算符和空格。整数除法仅保留整数部分。
示例1
输入:" 3+2*2"
输出:7
示例2:
输入:" 3/2"
输出:1
示例3:
输入:" 3+5 / 2"
输出:5
说明:
题目来源:https://leetcode-cn.com/problems/calculator-lcci/
**********下面有解法,请先自我思考 ************
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
解题思路
用栈解决,遇到加、减入栈,遇乘、除先计算再入栈;入栈完成后计算栈中元素和。
参考 https://leetcode-cn.com/problems/calculator-lcci/solution/javajie-ti-si-lu-by-hulu888/
import java.util.Stack;
class Solution {
public int calculate(String s) {
s = s.replaceAll(" ", "");
Stack<Integer> stack = new Stack<>();
char sign = '+';
int num = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if (!Character.isDigit(c) || i == n - 1) {
switch (sign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
case '/':
stack.push(stack.pop() / num);
break;
}
sign = c;
num = 0;
}
}
int res = 0;
while (!stack.isEmpty()) {
res += stack.pop();
}
return res;
}
}
测试一下
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();
List<String> cases = new ArrayList<>();
cases.add(" 3+2*2");
cases.add("3/2");
cases.add(" 3+5 / 2");
cases.add("3 + 6 * 2 + 1");
cases.add("3 + 6 / 2 * 4 / 15 ");
for (String s : cases) {
System.out.println(String.format("%s = %d", s, solution.calculate(s)));
}
}
}
输出
3+2*2 = 7
3/2 = 1
3+5 / 2 = 5
3 + 6 * 2 + 1 = 16
3 + 6 / 2 * 4 / 15 = 3
扩展
如果可以包含括号,那么如何去做呢?
如果可以包含括号,我们需要先转换成后缀表达式,然后再计算。
中缀表达式转后缀表达式步骤:
import java.util.Stack;
class Solution {
/**
* Operators in reverse order of precedence.
*/
private static final String operators = "+-*/";
private static final String operands = "0123456789";
public int calculate(String s) {
return evaluatePostfix(convert2Postfix(s));
}
private String convert2Postfix(String infixExpr) {
char[] chars = infixExpr.toCharArray();
Stack<Character> stack = new Stack<Character>();
StringBuilder out = new StringBuilder(infixExpr.length());
for (char c : chars) {
if (isOperator(c)) {
while (!stack.isEmpty() && stack.peek() != '(') {
if (operatorGreaterOrEqual(stack.peek(), c)) {
out.append(stack.pop());
} else {
break;
}
}
stack.push(c);
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
out.append(stack.pop());
}
if (!stack.isEmpty()) {
stack.pop();
}
} else if (isOperand(c)) {
out.append(c);
}
}
while (!stack.empty()) {
out.append(stack.pop());
}
return out.toString();
}
public int evaluatePostfix(String postfixExpr) {
char[] chars = postfixExpr.toCharArray();
Stack<Integer> stack = new Stack<Integer>();
for (char c : chars) {
if (isOperand(c)) {
stack.push(c - '0'); // convert char to int val
} else if (isOperator(c)) {
int op1 = stack.pop();
int op2 = stack.pop();
int result;
switch (c) {
case '*':
result = op1 * op2;
stack.push(result);
break;
case '/':
result = op2 / op1;
stack.push(result);
break;
case '+':
result = op1 + op2;
stack.push(result);
break;
case '-':
result = op2 - op1;
stack.push(result);
break;
}
}
}
return stack.pop();
}
private int getPrecedence(char operator) {
int ret = 0;
if (operator == '-' || operator == '+') {
ret = 1;
} else if (operator == '*' || operator == '/') {
ret = 2;
}
return ret;
}
private boolean operatorGreaterOrEqual(char op1, char op2) {
return getPrecedence(op1) >= getPrecedence(op2);
}
private boolean isOperator(char val) {
return operators.indexOf(val) >= 0;
}
private boolean isOperand(char val) {
return operands.indexOf(val) >= 0;
}
}
测试一下
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();
List<String> cases = new ArrayList<>();
cases.add(" 3+2*2");
cases.add("3/2");
cases.add(" 3+5 / 2");
cases.add("3 + 6 * 2 + 1");
cases.add("3 + 6 / 2 * 4 / 15 ");
cases.add("3 + 6 * (2 + 4) +1 ");
cases.add("(3 + 2) * (2 + 4) + 1 ");
for (String s : cases) {
System.out.println(String.format("%s = %d", s, solution.calculate(s)));
}
}
}
输出
3+2*2 = 7
3/2 = 1
3+5 / 2 = 5
3 + 6 * 2 + 1 = 16
3 + 6 / 2 * 4 / 15 = 12
3 + 6 * (2 + 4) +1 = 40
(3 + 2) * (2 + 4) + 1 = 31
参考
[1]. https://leetcode-cn.com/problems/calculator-lcci/solution/javajie-ti-si-lu-by-hulu888/
[2]. https://blog.csdn.net/zengxingyuluo/java/article/details/78934729