【练习】计算给定算数表达式的结果
题目
给定一个包含正整数、加（+）、减（-）、乘（*）、除（/）的算数表达式（括号除外），计算其结果。
表达式仅包含非负整数、+、-、*、/四种运算符和空格。整数除法仅保留整数部分。
示例1
输入：" 3+2*2"
输出：7示例2：
输入：" 3/2"
输出：1示例3：
输入：" 3+5 / 2"
输出：5说明：
- 你可以假设所给定的表达式都是有效的。
- 请不要使用内置的库函数eval
题目来源：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
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读