请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：
，保证计算结果始终在整型范围内
要求：空间复杂度： )
，时间复杂度
[编程题]表达式求值
import java.util.*;
// 计算器
public class Solution {
public int solve (String s) {
int n = s.length();
return dfs(s.toCharArray(), 0, n - 1);
}
int dfs(char[] s, int L, int R) {
Deque<Integer> nums = new ArrayDeque<>(); // 数字
Deque<Integer> ops = new ArrayDeque<>(); // 运算符
int[] prior = new int[128]; // 优先级
prior['+'] = prior['-'] = 1;
prior['*'] = prior['/'] = 2;
nums.push(0); // 开头负号
int n = s.length;
for (int i = L; i <= R; i++) {
int c = s[i];
if (c >= '0' && c <= '9') {
int x = c-'0';
while (++i < n && s[i] >= '0' && s[i] <= '9' ) {
x = x * 10 + s[i] - '0';
}
i--;
nums.push(x);
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
calc(nums, ops, prior, c);
} else { //（
int j = i + 1, level = 1;
while (level > 0) {
if (s[j] == '(') level++;
else if (s[j] == ')') level--;
j++;
}
nums.push(dfs(s, i + 1, j - 2));
i = j - 1;
}
}
calc(nums, ops, prior, '+'); // 计算栈内剩余元素
return nums.pop();
}
// 新运算符c：栈内更高优先级的先算
void calc(Deque<Integer> nums, Deque<Integer> ops, int[] prior, int c) {
while (!ops.isEmpty() && nums.size() > 1 && prior[ops.peek()] >= prior[c]) {
int op = ops.pop();
int y = nums.pop(), x = nums.pop();
if (op == '+') x += y;
else if (op == '-') x -= y;
else if (op == '*') x *= y;
else if (op == '/') x /= y;
nums.push(x);
}
ops.push(c);
}
}
发表于 2025-10-18 11:49:21
回复(0)
看spring 源码 org.springframework.core.env.ProfilesParser#parse 方法时弱有所思，然后结合官方的解法输出的代码，过程中用到了栈，主要思路是遇到左括号递归子过程，遇到右括号跳出子过程，并将子过程的返回值给上层参与运算，如果遇到了数字（操作数） 则判断上一次的操作符是什么，如果是* 则将栈顶元素和当前数字做乘法计算并将计算结果入栈，如果是- 将相反数思路入栈，其他情况直接入栈 也和官方的解法差不多 ，运用了StringTokenizer 类来解析操作数与操作符
import java.util.*;
import java.util.StringTokenizer;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
StringTokenizer tokenizer = new StringTokenizer(s, "+-*()", true);
return calc(tokenizer);
}
public Integer calc(StringTokenizer tokenizer) {
String lastOper = null;
Stack<Integer> currentStack = new Stack<>();
while (tokenizer.hasMoreTokens()) {
String token = tokenizer.nextToken();
System.out.println(token);
switch (token) {
case "(":
Integer subRes = calc(tokenizer);
if (lastOper != null && "*".equals(lastOper)) {
currentStack.push(currentStack.pop() * subRes);
} else if (lastOper != null && "-".equals(lastOper)) {
currentStack.push(0 - subRes);
} else {
currentStack.push(subRes);
}
lastOper = "(";
break;
case ")":
Integer subSum = 0;
while (!currentStack.isEmpty()) {
subSum += currentStack.pop();
}
return subSum;
case "+":
lastOper = "+";
break;
case "-":
lastOper = "-";
break;
case "*":
lastOper = "*";
break;
default:
// 数值
if (lastOper != null && "*".equals(lastOper)) {
currentStack.push(currentStack.pop() * Integer.parseInt(token));
} else if (lastOper != null && "-".equals(lastOper)) {
currentStack.push(0 - Integer.parseInt(token));
} else {
currentStack.push(Integer.parseInt(token));
}
}
}
Integer total = 0;
while (!currentStack.isEmpty()) {
total += currentStack.pop();
}
return total;
}
发表于 2025-09-07 17:06:47
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
// write code here
// 使用双栈分别存放操作符和数字
Deque<Character> ops = new ArrayDeque<>();
Deque<Integer> nums = new ArrayDeque<>();
ops.push('#');
s += "#";
for(int i = 0;i < s.length();i++)//遍历s
{
char c = s.charAt(i);
if(c >= '0' && c <= '9')//如果是数字，则处理后入栈
{
if(i == 0)
{
int num = c - '0';
nums.push(num);
continue;
}
else
{
char pre = s.charAt(i - 1);
if(pre >= '0' && c <= '9')
{
int num = nums.pop() * 10 + (c - '0');
nums.push(num);
}
else
{
int num = c - '0';
nums.push(num);
}
continue;
}
}
else//如果是操作符，根据优先级() > * > +/-操作
{
if(c == '-' || c == '+' || c == '#')
{
if(c == '-' && (i == 0 || s.charAt(i - 1) == '('))
{
nums.push(0);
ops.push('-');
continue;
}
// if(c == '+' && (i == 0 || s.charAt(i - 1) == '('))
// {
// continue;
// }
while(ops.peek() == '*' || ops.peek() == '+' || ops.peek() == '-')
{
int b = nums.pop();
int a = nums.pop();
char op = ops.pop();
switch(op)
{
case '*':
nums.push(a * b);
break;
case '+':
nums.push(a + b);
break;
case '-':
nums.push(a - b);
break;
}
}
ops.push(c);
}
if(c == '(')
{
ops.push(c);
}
if(c == ')')
{
while(ops.peek() != '(')
{
int b = nums.pop();
int a = nums.pop();
char op = ops.pop();
switch(op)
{
case '*':
nums.push(a * b);
break;
case '+':
nums.push(a + b);
break;
case '-':
nums.push(a - b);
break;
}
}
ops.pop();
}
if(c == '*')
{
ops.push(c);
}
}
}
return nums.peek();
}
}
发表于 2025-07-11 10:39:43
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
int result = 0;
String num = "";
Stack<Integer> numberStack = new Stack<>();
Stack<Character> characterStack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
// 数字栈
if (Character.isDigit(ch)) {
// 如果是计算式的最后一位
if (i + 1 == s.length()) {
num = num + String.valueOf(ch);
numberStack.push(Integer.parseInt(num));
num = "";
//或者后面一位没有数字
} else if (!Character.isDigit(s.charAt(i + 1))) {
num = num + String.valueOf(ch);
numberStack.push(Integer.parseInt(num));
num = "";
// 后面一位有数字，是一个多位数
} else {
num = num + String.valueOf(ch);
}
}
// 遇到运算符
if (!Character.isDigit(ch)) {
if(ch == '('){
characterStack.push(ch);
}else if(ch == ')'){// 遇到）时准备计算括号内表达式
while(characterStack.peek()!='('){
caculate(numberStack,characterStack);
}
characterStack.pop();// 把左括号出栈
}else{
//不止第一次遇见运算符、且在该情况下遇见的运算符优先级低于或等于等待预算的运算符
while(!characterStack.isEmpty()&&getPriority(ch)<=getPriority(characterStack.peek())){
caculate(numberStack,characterStack);
}
// 第一次遇见运算符、或连续遇见低级运算符
characterStack.push(ch);
}
}//示例只有低级运算符
}
while(!characterStack.isEmpty()){
caculate(numberStack,characterStack);
}
result = numberStack.pop();
return result;
}
public void caculate(Stack<Integer> numberStack,Stack<Character> characterStack) {
int x = numberStack.pop();
int y = numberStack.pop();
char z = characterStack.pop();
int res = 0;
if (z == '+') {
res = y + x;
} else if (z == '-') {
res = y - x;
} else if (z == '*') {
res = y * x;
}
numberStack.push(res);
}
private int getPriority(char ch){
if(ch == '+'||ch == '-'){
return 1;
}else if(ch == '*'){
return 2;
}
return -1;
}
}
发表于 2025-04-04 20:34:55
回复(0)
import java.util.*;
/**
* NC137 表达式求值
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 相似 -> NC240 计算器(一) [nowcoder]
* 相似 -> NC241 计算器(二) [nowcoder]
* 相似 -> HJ50 四则运算 [nowcoder]
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
int n = s.length();
if(n == 0){
return 0;
}
Stack<Integer> stack = new Stack<>();
char sign = '+';
int num;
char ch;
for(int i=0; i<n; i++){
num = 0;
ch = s.charAt(i);
// 数字
if(Character.isDigit(ch)){
num = num*10+(ch-'0');
while(++i < n){
ch = s.charAt(i);
if(Character.isDigit(ch)){
num = num*10+(ch-'0');
}else{
break;
}
}
}
// 括号 -> 递归
if(ch == '('){
int cnt = 1;
int j;
for(j=i+1; j<n; j++){
ch = s.charAt(j);
if(ch == '('){
cnt++;
}
else if(ch == ')'){
cnt--;
}
if(cnt == 0){
num = solve(s.substring(i+1, j));
break;
}
}
i = j+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;
default: break;
}
if(i == n){
break;
}else{
sign = s.charAt(i);
}
}
int result = 0;
while(!stack.isEmpty()){
result += stack.pop();
}
return result;
}
}
发表于 2025-01-28 14:44:23
回复(0)
实现个parser用ast计算，加减乘除都能算。就是代码长了。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
ArrayList<String> tokens = splite(s);
// System.out.println("tokens: " + tokens);
ExprAst ast = parse(tokens);
return ast.eval();
}
private ArrayList<String> splite(String s) {
ArrayList<String> ret = new ArrayList<>();
StringBuilder buffer = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
if (ch == ' ' || ch == '\t') continue;
if (ch >= '0' && ch <= '9') {
buffer.append(ch);
} else {
if (buffer.length() > 0) {
ret.add(buffer.toString());
buffer.setLength(0);
}
ret.add("" + ch);
}
}
if (buffer.length() > 0)
ret.add(buffer.toString());
return ret;
}
private ExprAst parse(ArrayList<String> tokens) {
TokenList tokenlst = new TokenList();
tokenlst.tokens = tokens;
tokenlst.position = 0;
ExprAst ast = new ExprParser().init().parse(tokenlst);
return ast;
}
private static class TokenList {
public ArrayList<String> tokens;
public int position;
public boolean isEnd() {
return position == tokens.size();
}
public String nextToken() {
return tokens.get(position++);
}
public String peek() {
return peekN(0);
}
public String peekN(int n) {
return tokens.get(position + n);
}
}
// expr = Num | subExpr [binOp expr]
// subExpr = '('expr')'
private static abstract class AbsParser {
protected ExprAst prevAst = null;
abstract boolean isMatch(TokenList tokens);
abstract ExprAst parse(TokenList tokens);
AbsParser setPrevAst(ExprAst ast) {
prevAst = ast;
return this;
}
}
private static AstBinOp getToAddInPrev(ExprAst prev) {
ExprAst toAdd = prev;
while (true) {
if (toAdd instanceof AstBinOp) {
if (null == ((AstBinOp)toAdd).right()) {
break;
}
toAdd = ((AstBinOp)toAdd).right();
} else if (toAdd instanceof AstSubExpr) {
toAdd = ((AstSubExpr)toAdd).subExpr();
} else {
return null;
}
}
return (AstBinOp) toAdd;
}
private static class NumParser extends AbsParser {
@Override
boolean isMatch(TokenList tokens) {
String token = tokens.peek();
for (int i = 0; i < token.length(); ++i) {
char ch = token.charAt(i);
if (ch < '0' || ch > '9') return false;
}
return true;
}
@Override
ExprAst parse(TokenList tokens) {
ExprAst lprev = prevAst;
String t = tokens.nextToken();
ExprAst ast = new AstNum().setValue(Integer.parseInt(t));
AstBinOp toAdd = getToAddInPrev(lprev);
if (toAdd != null) {
toAdd.setRight(ast);
return lprev;
}
return ast;
}
}
private static class BinOpParser extends AbsParser {
// 操作符和优先级定义
private static final Map<String, Integer> opMap = new HashMap<>();
static {
opMap.put("%", 0);
opMap.put("+", 1);
opMap.put("-", 1);
opMap.put("*", 2);
opMap.put("/", 2);
}
@Override
boolean isMatch(TokenList tokens) {
return opMap.containsKey(tokens.peek());
}
@Override
ExprAst parse(TokenList tokens) {
ExprAst lprev = prevAst;
String op = tokens.nextToken();
AstBinOp ast = new AstBinOp(op);
ast.setLeft(lprev);
if (lprev instanceof AstBinOp) {
AstBinOp preBinOpAst = ((AstBinOp)lprev);
String preOp = preBinOpAst.getOp();
if (opMap.get(op) > opMap.get(preOp)) {
// 当前优先级更高
ExprAst preRight = preBinOpAst.right();
((AstBinOp)lprev).setRight(ast);
ast.setLeft(preRight);
ast = preBinOpAst;
}
}
return ast;
}
}
private static class ExprParser extends AbsParser {
private AbsParser startParser = null;
private AbsParser maybeParser = null;
public ExprParser init() {
startParser = new OrParser().setParsers(new NumParser(), new SubExprParser().setContentParser(this));
maybeParser = new MaybeParser().setParsers(new BinOpParser(), this);
return this;
}
@Override
boolean isMatch(TokenList tokens) {
return startParser.isMatch(tokens);
}
@Override
ExprAst parse(TokenList tokens) {
ExprAst ast = startParser.setPrevAst(prevAst).parse(tokens);
return maybeParser.setPrevAst(ast).parse(tokens);
}
}
private static class SubExprParser extends AbsParser {
AbsParser contentParser = null;
public SubExprParser setContentParser(AbsParser parser) {
contentParser = parser;
return this;
}
@Override
boolean isMatch(TokenList tokens) {
String t = tokens.peek();
return "(".equals(t);
}
@Override
ExprAst parse(TokenList tokens) {
ExprAst lprev = prevAst;
tokens.nextToken(); // for (
ExprAst content = contentParser.setPrevAst(null).parse(tokens);
tokens.nextToken(); // for )
ExprAst ast = new AstSubExpr().setContent(content);
// System.out.println("sub parser" + " ast=" + ast + " pre=" + prevAst + " at " + tokens.peek());
AstBinOp toAdd = getToAddInPrev(lprev);
if (toAdd != null) {
toAdd.setRight(ast);
// System.out.println("sub parse res=" + prevAst);
return lprev;
}
return ast;
}
}
private static class MaybeParser extends AbsParser {
private AbsParser[] parsers;
public MaybeParser setParsers(AbsParser... parsers) {
this.parsers = parsers;
return this;
}
@Override
public boolean isMatch(TokenList tokens) {
if (tokens.isEnd() || tokens.peek().equals(")")) return true;
if (parsers[0].isMatch(tokens)) return true;
return false;
}
public ExprAst parse(TokenList tokens) {
ExprAst ast = prevAst;
while (!tokens.isEnd() && !tokens.peek().equals(")")) {
for (AbsParser parser: parsers) {
ast = parser.setPrevAst(ast).parse(tokens);
}
}
return ast;
}
}
private static class OrParser extends AbsParser {
private AbsParser[] parsers;
public OrParser setParsers(AbsParser... parsers) {
this.parsers = parsers;
return this;
}
@Override
boolean isMatch(TokenList tokens) {
for (AbsParser p : parsers) {
if (p.isMatch(tokens)) return true;
}
return false;
}
@Override
ExprAst parse(TokenList tokens) {
ExprAst lprev = prevAst;
for (AbsParser p: parsers) {
if (p.isMatch(tokens)) {
return p.setPrevAst(lprev).parse(tokens);
}
}
throw new IllegalStateException("error in&nbs***bsp;parser");
}
}
private static abstract class ExprAst {
protected ArrayList<ExprAst> children = new ArrayList<>();
public abstract int eval();
}
private static class AstNum extends ExprAst {
private int v;
public AstNum setValue(int v) {
this.v = v;
return this;
}
public int getValue() {
return v;
}
@Override
public int eval() {return v;}
@Override
public String toString() {
return "n(" + v + ")";
}
}
private static class AstSubExpr extends ExprAst {
public AstSubExpr() {
children.add(null);
}
public AstSubExpr setContent(ExprAst expr) {
children.set(0, expr);
return this;
}
public ExprAst subExpr() {
return children.get(0);
}
@Override
public int eval() {
return subExpr().eval();
}
@Override
public String toString() {
return "SubExpr(" + subExpr() + ")";
}
}
private static class AstBinOp extends ExprAst {
private String op;
public AstBinOp(String op) {
this.op = op;
children.add(null);
children.add(null);
}
public String getOp() {
return this.op;
}
private ExprAst left() {
return children.get(0);
}
private ExprAst right() {
return children.get(1);
}
private AstBinOp setLeft(ExprAst l) {
children.set(0, l);
return this;
}
private AstBinOp setRight(ExprAst r) {
children.set(1, r);
return this;
}
public int eval() {
int lv = left().eval();
int rv = right().eval();
switch (op) {
case "+":
return lv + rv;
case "-":
return lv - rv;
case "*":
return lv * rv;
case "/":
return lv / rv;
case "%":
return lv % rv;
}
throw new IllegalStateException("invalid bin op ast in eval op=" + op);
}
@Override
public String toString() {
return "BinOp(op=" + op + "left=" + left() + ",right=" + right() + ")";
}
}
}
发表于 2024-12-26 10:49:43
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
int n = s.length();
Stack<Character> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == '(') {
s1.push(ch);
} else if (ch == ')') {
while (s1.peek() != '(') {
caculate(s1, s2);
}
s1.pop();
} else if (s.charAt(i) <= '9' && s.charAt(i) >= '0') {
StringBuilder sb = new StringBuilder();
while (i < n && s.charAt(i) <= '9' && s.charAt(i) >= '0') {
sb.append(s.charAt(i));
i++;
}
s2.push(Integer.parseInt(sb.toString()));
i--;
} else {
while (!s1.isEmpty() && ch != '*' && s1.peek() != '(') {
caculate(s1, s2);
}
s1.push(ch);
}
}
int res = 0;
while (!s1.isEmpty()) {
caculate(s1, s2);
}
return s2.pop();
}
private void caculate(Stack<Character> s1, Stack<Integer> s2) {
int b = s2.pop();
int a = s2.pop();
char op = s1.pop();
int ans = a - b;
if (op == '+') {
ans = a + b;
} else if (op == '*') {
ans = a * b;
}
s2.push(ans);
}
}
发表于 2024-10-08 21:21:02
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public static int solve(String s) {
// write code here
ArrayList<Integer> res = sumFunction(s, 0);
return res.get(0);
}
public static ArrayList<Integer> sumFunction(String s, int index) {
Stack<Integer> numStack = new Stack<>();
int num = 0;
char op = '+';
int i = 0;
for (i = index; i < s.length(); i++) {
// 取出数字num
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
num = num * 10 + s.charAt(i) - '0';
if (i != s.length() - 1) {
continue;
}
}
// 进入递归
if (s.charAt(i) == '(') {
ArrayList<Integer> list = sumFunction(s, i + 1);
num = list.get(0);
i = list.get(1);
if (i != s.length() - 1) {
continue;
}
}
switch (op) {
case '+':
numStack.push(num);
break;
case '-':
numStack.push(-num);
break;
case '*':
int temp = numStack.pop();
numStack.push(temp * num);
break;
}
num = 0;
if (s.charAt(i) == ')') { // 退出递归
break;
} else {
op = s.charAt(i);
}
}
int sum = 0;
for (int j = 0; j < numStack.size(); j++) {
sum += numStack.get(j);
}
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(sum);
list.add(i);
return list;
}
}
发表于 2024-06-04 16:07:05
回复(0)
解决这个问题有3个地方要处理：
- 拆解字符串
- 按优先级处理（重点）
- 最后将剩余的元素依次计算即可
- 两个低优先级符号中间如果夹着高优先级符号，要先把高优先级的结果先算出来
- 两个括号之间的结果要先算出来
代码如下：有点长
/**
* @author tt
* @Date Created in 2024/4/10 下午4:21
*/
public static int solve(String s) {
Set<String> symbol = Stream.of("+", "-", "*", "(", ")").collect(Collectors.toSet());
Deque<String> symbolStack = new ArrayDeque<>();
Deque<Integer> numberStack = new ArrayDeque<>();
List<String> stringList = getStringList(s);
for (String str : stringList) {
if (!symbol.contains(str)) { // 数字
numberStack.push(Integer.valueOf(str));
} else { // 符号
switch (str) {
case "+":
case "-":
while ("*".equals(symbolStack.peek())) {
int opt2 = numberStack.poll();
int opt1 = numberStack.poll();
symbolStack.poll();
numberStack.push(opt1 * opt2);
}
symbolStack.push(str);
break;
case "*":
case "(":
symbolStack.push(str);
break;
case ")":
Deque<String> tempSymbolStack = new ArrayDeque<>();
Deque<Integer> tempNumberStack = new ArrayDeque<>();
while (!"(".equals(symbolStack.peek())) {
tempSymbolStack.addLast(symbolStack.poll());
tempNumberStack.addLast(numberStack.poll());
}
tempNumberStack.addLast(numberStack.poll());
symbolStack.poll();
while ("*".equals(tempSymbolStack.peek())) {
int opt2 = tempNumberStack.poll();
int opt1 = tempNumberStack.poll();
tempSymbolStack.poll();
tempNumberStack.push(opt1 * opt2);
}
while (!tempSymbolStack.isEmpty()) {
String currentSymbol = tempSymbolStack.pollLast();
int opt1 = tempNumberStack.pollLast();
int opt2 = tempNumberStack.pollLast();
tempNumberStack.addLast(compute(opt1, opt2, currentSymbol));
}
numberStack.push(tempNumberStack.poll());
break;
}
}
}
// 最后执行一次普通运算
while ("*".equals(symbolStack.peek())) {
int opt2 = numberStack.poll();
int opt1 = numberStack.poll();
symbolStack.poll();
numberStack.push(opt1 * opt2);
}
while (!symbolStack.isEmpty()) {
String currentSymbol = symbolStack.pollLast();
int opt1 = numberStack.pollLast();
int opt2 = numberStack.pollLast();
numberStack.addLast(compute(opt1, opt2, currentSymbol));
}
return numberStack.peek();
}
private static int compute(int opt1, int opt2, String currentSymbol) {
switch (currentSymbol) {
case "*":
return opt1 * opt2;
case "+":
return opt1 + opt2;
case "-":
return opt1 - opt2;
}
return 0;
}
/**
* 拆解字符串
*
* @param s 原始字符串
* @return 将数字和符号拆解
* @author tt
* @Date Created in 2024/4/10 下午4:22
*/
private static List<String> getStringList(String s) {
List<String> strList = new ArrayList<>();
StringBuilder stringBuilder = new StringBuilder();
Set<String> numberSet = Stream.of("1", "2", "3", "4", "5", "6", "7", "8", "9", "0").collect(Collectors.toSet());
for (String str : s.split("")) {
// 判断是否为数字
if (numberSet.contains(str)) {
stringBuilder.append(str);
} else {
if (stringBuilder.length() != 0) {
strList.add(stringBuilder.toString());
stringBuilder = new StringBuilder();
}
strList.add(str);
}
}
if (stringBuilder.length() != 0) {
strList.add(stringBuilder.toString());
}
return strList;
}
编辑于 2024-04-10 17:09:45
回复(0)
老老实实的对各种可能性进行判断，进栈入栈，代码可能很长，但是自我感觉还是挺条理清晰的
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
// write code here
if(s.isEmpty()){
return 0;
}
if(s.length() == 1){
return Integer.parseInt(s);
}
//存储数字的栈
Stack<String> sStack = new Stack<>();
//存储符号的栈
Stack<String> sSymbol = new Stack<>();
//临时存储数字字符串--防止有两位的数字
String tempIntString = "";
int sLength = s.length();
for(int i = 0;i < sLength;i++){
String symbol = String.valueOf(s.charAt(i));
//如果符号为(则直接添加到符号栈
if(symbol.equals("(")){
sSymbol.push(symbol);
}else if(symbol.equals("*")){
//如果符号为*则进行判断
if(!tempIntString.isEmpty()){
//如果存储数字字符不为空，
if(!sSymbol.isEmpty()){
//并且符号栈部位空最后一个也为*
if(sSymbol.peek().equals("*")){
//除去乘号
sSymbol.pop();
//数字栈添加进行乘法运算后的数字
sStack.push(String.valueOf(Integer.parseInt(sStack.pop()) * Integer.parseInt(tempIntString)));
tempIntString = "";
sSymbol.push(symbol);
}else{
//符号栈最后一个不是乘号
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
//符号栈为空
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
//存储数字字符串为空时，直接符号入栈
sSymbol.push(symbol);
}
}else if(symbol.equals("-")){
//存储数字字符串不为空，那么-号就不可能是负数
if(!tempIntString.isEmpty()){
//如果符号栈不为空，
if(!sSymbol.isEmpty()){
//数字栈也不为空
if(!sStack.isEmpty()){
//符号栈最后一个为*
if(sSymbol.peek().equals("*")){
int leftNum = Integer.parseInt(sStack.pop());
sStack.push(String.valueOf((leftNum) * (Integer.parseInt(tempIntString))));
tempIntString = "";
//删除*
sSymbol.pop();
//添加-
sSymbol.push(symbol);
}else{
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
//数字栈为空
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
//符号栈为空
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
//存储数字字符串为空时
if(sStack.isEmpty()){
//数字栈也为空，那就负号
tempIntString = tempIntString.concat("-");
}else{
//数字栈不为空,符号栈也不为空
if(!sSymbol.isEmpty()){
//符号栈是(，那也是负号
if(sSymbol.peek().equals("(")){
tempIntString = tempIntString.concat("-");
}else{
sSymbol.push(symbol);
}
}else{
//其他情况都是符号
sSymbol.push(symbol);
}
}
}
}else if(symbol.equals("+")){
//存储数字字符串不为空
if(!tempIntString.isEmpty()){
//符号栈不为空
if(!sSymbol.isEmpty()){
//数字栈也不为空
if(!sStack.isEmpty()){
//符号栈最后一个为*
if(sSymbol.peek().equals("*")){
int leftNum = Integer.parseInt(sStack.pop());
sStack.push(String.valueOf((leftNum) * (Integer.parseInt(tempIntString))));
tempIntString = "";
sSymbol.pop();
sSymbol.push(symbol);
}else{
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
sStack.push(tempIntString);
tempIntString = "";
sSymbol.push(symbol);
}
}else{
//数字字符串为空时,不管什么情况它都是符号
sSymbol.push(symbol);
}
}else if(symbol.equals(")")){
//当数字字符串不为空时
if(!tempIntString.isEmpty()){
int rightNum = Integer.parseInt(tempIntString);
tempIntString = "";
while(!sSymbol.peek().equals("(")){
String tempSymbol = sSymbol.pop();
int leftInt = Integer.parseInt(sStack.pop());
if(tempSymbol.equals("+")){
rightNum = (leftInt) + (rightNum);
}else if(tempSymbol.equals("-")){
rightNum = (leftInt) - (rightNum);
}else{
rightNum = (leftInt) * (rightNum);
}
}
sStack.push(String.valueOf(rightNum));
//删除(
sSymbol.pop();
}else{
//数字字符串为空时,,此时存在的可能性就是在()中进行了一次乘法运算
int rightNum = Integer.parseInt(sStack.pop());
while(!sSymbol.peek().equals("(")){
String tempSymbol = sSymbol.pop();
int leftInt = Integer.parseInt(sStack.pop());
if(tempSymbol.equals("+")){
rightNum = (leftInt) + (rightNum);
}else if(tempSymbol.equals("-")){
rightNum = (leftInt) - (rightNum);
}else{
rightNum = (leftInt) * (rightNum);
}
}
sStack.push(String.valueOf(rightNum));
//删除(
sSymbol.pop();
}
//判断括号中运算完成后的第一个符号是否为*
if(!sSymbol.isEmpty() && sSymbol.peek().equals("*")){
int rightNum = Integer.parseInt(sStack.pop());
sSymbol.pop();
int leftNum = Integer.parseInt(sStack.pop());
sStack.push(String.valueOf((leftNum) * (rightNum)));
}
}else{
//数字的时候
tempIntString = tempIntString.concat(symbol);
}
}
//清空数字栈和符号栈，此时符号栈中只有+,-
if(!tempIntString.isEmpty()){
sStack.push(tempIntString);
tempIntString = "";
}
//最后要么只剩乘法，要么只剩加减，栈中的数字倒过来，由左至右正常加减乘即可
Stack<String> sSymbolReverse = new Stack<>();
Stack<String> sStackReverse = new Stack<>();
while(!sSymbol.isEmpty()){
sSymbolReverse.push(sSymbol.pop());
}
while(!sStack.isEmpty()){
sStackReverse.push(sStack.pop());
}
while(!sSymbolReverse.isEmpty()){
int leftNum = Integer.parseInt(sStackReverse.pop());
String tempSymbol = sSymbolReverse.pop();
int rightNum = Integer.parseInt(sStackReverse.pop());
if(tempSymbol.equals("+")){
rightNum = (leftNum) + (rightNum);
}else if(tempSymbol.equals("-")){
rightNum = (leftNum) - (rightNum);
}else{
rightNum = (leftNum) * (rightNum);
}
sStackReverse.push(String.valueOf(rightNum));
}
return Integer.parseInt(sStackReverse.pop());
}
}
编辑于 2024-03-11 10:24:49
回复(0)
HashMap<Character ,Integer> map=new HashMap<Character ,Integer>(){{
put('+' ,1);
put('-' ,1);
put('*' ,2);
}};
public int solve (String s) {
// write code here
Stack<Character> s1=new Stack<>();
Stack<Integer> s2=new Stack<>();
s2.push(0);
char[] cs=s.replaceAll(",","").toCharArray();
for(int i=0;i<cs.length;i++){
// 1、遇到左括号
if(cs[i]=='('){
s1.push('(');
}else if(Character.isDigit(cs[i])){ //2、遇到数字
int num=0;
while(i<cs.length && Character.isDigit(cs[i])){
num=num*10+(cs[i++]-'0');
}
i--;
s2.push(num);
}else if(cs[i]==')'){// 3、遇到右括号
while(s1.peek()!='('){
cacl(s1 ,s2);
}
s1.pop();
}else{// 4、遇到计算符号
if(i>0 && cs[i-1]=='('){ // 4.1 如果左括号后紧跟一个计算符号，需要在符号前加个0 ，便于进行计算
s2.push(0);
} // 4.2 符号优先级高的会先进行计算
while(!s1.isEmpty() && s1.peek()!='(' && map.get(cs[i])<=map.get(s1.peek())){
cacl(s1 ,s2);
} // 4.3 处理完紧跟左括号和优先级计算，需要将当前的符号压栈
s1.push(cs[i]);
}
}
// 5、将没计算完的情况进行计算，如只有1+2
while(!s1.isEmpty()){
cacl(s1 ,s2);
}
return s2.pop();
}
public void cacl(Stack<Character> s1 ,Stack<Integer> s2){
if(s1.size()<1 || s2.size()<2){
return;
}
char c=s1.pop();
int n=s2.pop() ,m=s2.pop();
if(c=='+'){
s2.push(m+n);
}else if(c=='-'){
s2.push(m-n);
}else{
s2.push(m*n);
}
}
编辑于 2024-03-03 12:54:32
回复(0)
时间超时啊
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
// write code here
int result = 0;
List<String> transList = transList(s);
System.out.println(transList);
List<String> reversePolish = reversePolish(transList);
System.out.println(reversePolish);
result = calculate(reversePolish);
return result;
}
private int calculate(List<String> reversePolish) {
// TODO
Stack<String> temp = new Stack<>();
reversePolish.stream().forEach(e-> {
if (e.matches("//d")) {
temp.add(e);
} else {
int num1 = Integer.parseInt(temp.pop());
int num2 = Integer.parseInt(temp.pop());
int res = calc(num1, num2, e);
temp.add(res + "");
}
});
return Integer.parseInt(temp.pop());
}
private int calc(int num1, int num2, String e) {
// TODO
int res = 0;
switch (e) {
case "+":
res = num1 + num2;
break;
case "-":
res = num1 - num2;
break;
case "*":
res = num1 * num2;
break;
case "/":
res = num1 / num2;
break;
}
return res;
}
private List<String> reversePolish(List<String> transList) {
// TODO
List<String> res = new ArrayList<>(); // 队列，用于保存后缀表达式
Stack<String> opt = new Stack<>(); //暂时保存运算符的栈
transList.stream().forEach(e-> {
if (e.matches("//d")) { // 正则表达式来判断，如果是数字，则直接入队；
res.add(e);
} else {
if (e.equals("(")) { // 若是左括号，直接入运算符栈
opt.add("(");
} else if (
e.equals(")")) { // 如果是右括号，则将运算符栈中的运算符出栈 并入队到表达式队列中
while (!opt.isEmpty() && !opt.peek().equals("(")) {
res.add(opt.pop());
}
opt.pop(); // 最后把左括号出栈;
} else {
// 如过是四则运算符+ - * /,则先和运算符栈顶元素比较优先级,若优先级比栈顶的高则直接入栈，
// 否则将运算符栈出栈并入到表达式队列,直到优先级大于栈顶元素，再入栈
while (!opt.isEmpty() && getValue(opt.peek()) >= getValue(e)) {
res.add(opt.pop());
}
opt.add(e);
}
}
});
while (!opt.isEmpty()) {
res.add(opt.pop());
}
return res;
}
private int getValue(String opt) {
// TODO
int reslut = 0;
switch (opt) {
case "+":
reslut = 1;
break;
case "-":
reslut = 1;
break;
case "*":
reslut = 2;
break;
case "/":
reslut = 2;
break;
}
return reslut;
}
private List<String> transList(String s) {
// TODO
List<String> express = new ArrayList<>();
int i = 0;
String str; // 用于拼接多位数字
while (i < s.length()) {
char ch = s.charAt(i);
if (ch < 48 || ch > 57) {
express.add(ch + "");
} else {
str = "";
while (i < s.length() && (s.charAt(i) >= 48 && s.charAt(i) <= 57)) {
str = str + s.charAt(i) + "";
i++;
}
express.add(str);
}
}
return express;
}
}
编辑于 2024-01-24 14:21:02
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
// 存放操作数
Stack<Integer> nums = new Stack<Integer>();
// 存放运算符
Stack<Character> ops = new Stack<Character>();
// 维护运算符优先级,数字越大优先级越高
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
public int solve (String s) {
// write code here
map.put('+', 1);
map.put('-', 1);
map.put('*', 2);
// 遍历表达式
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
// 遇到数字
if (Character.isDigit(ch)) {
int num = 0;
int j = i;
// 判断是否为多位数
while (j < s.length() && Character.isDigit(s.charAt(j))) {
num = s.charAt(j++) - '0' + num * 10;
}
// 将数字加入操作数集
nums.push(num);
// 下轮循环i应该从数字的后一位开始，即j-1，因为while中j < s.length()时
// j指向了数字的下一位，如果令i=j，则for过程i++时，i将从数字下下一位开始
i = j - 1;
// ops为空，运算符和左括号直接入栈
} else if (ops.size() == 0 && ch != ')') {
ops.push(ch);
}
// 遇到左括号直接入栈
else if (ch == '(') {
ops.push(ch);
}
// 遇到右括号，则计算，运算符出栈（由eval完成），直到遇到栈顶为左括号，并舍弃左右括号。左括号前的运算符
// 会在eval()中出栈
else if (ch == ')') {
while (ops.peek() != '(') {
eval();
}
ops.pop();
}
// 遇到运算符
else {
// 运算符栈不为空，且栈顶元素不为左括号且当前运算符优先级不大于栈顶运算符优先级，
// 则对ops弹栈通过eval()进行运算，ops弹栈由eval计算过程中完成，计算直到栈顶的
// 运算符优先级小于当前运算符优先级为止，并将当前运算符入栈
while (ops.size() != 0 && ops.peek() != '(' && map.get(ops.peek()) >= map.get(ch)) {
eval();
}
ops.push(ch);
}
}
// 栈中还有运算符时，循环运算至ops为空
while (ops.size() != 0) {
eval();
}
// 最后栈中只剩下计算结果，直接弹栈
return nums.pop();
}
// 计算
public void eval() {
int b = nums.pop();
int a = nums.pop();
char c = ops.pop();
int res = 0;
switch (c) {
case '+':
res = a + b;
break;
case '-':
res = a - b;
break;
case '*':
res = a * b;
break;
}
// if(c=='+') res = a + b;
// else if (c=='-') res = a - b;
// else if (c=='*') res = a * b;
nums.push(res);
}
}
发表于 2023-10-13 22:14:55
回复(0)
import java.util.*;
public class Solution {
/**
* 遍历中缀表达式
* 如果是数字
* 1、数字前一个字符不是数字则在后缀表达式中加入 ' '
* 2、数字是第一个或者前一个是数字，直接加入后缀表达式
* 如果是运算符：
* 1、'(' 直接入栈
* 2、')' 将栈中元素取出加入到后缀表达式，直到取出一个 '(' ，'(' 不加入后缀表达式
* 3、如果是 '+' 或 '-' 将栈中元素取出加入后缀表达式，直到栈为空 或者 栈顶元素为 '('
* 4、如果是 '*' 或 '/' 将栈中元素取出加入后缀表达式，直到栈为空 或者 栈顶元素不为 '*' 或者 '/'
* 遍历结束后，将栈中元素全部取出加入后缀表达式
* 后缀表达式求值
* 如果是数字
* 1、遍历找到下一个不是数字的字符下标，截取出这个完整数字加入栈
* 如果是空格直接跳过
* 如果是 '+' 或 '-' 或 '*' 或 '/',从栈中取出两个数字进行计算，并将计算结果加入栈
* （注：先取出的在原算符后面，后取出的在运算符前面）
* 遍历后缀表达式结束，取出栈中元素即为最终结果
*/
public int solve (String s) {
// write code here
String str = infixToSuffix(s);
return suffixValue(str);
}
/**
* 中缀表达式转换成后缀表达式（逆波兰表达式）
*/
public static String infixToSuffix (String s) {
// 存储运算符
Stack<Character> stack = new Stack<>();
// 存储后缀表达式
StringBuilder s1 = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(c);
continue;
}
if (c == ')') {
Character pop = stack.pop();
while (pop != '(') {
s1.append(" ").append(pop);
pop = stack.pop();
}
continue;
}
if (c == '+' || c == '-') {
while (!stack.isEmpty() && stack.peek() != '(') {
s1.append(" ").append(stack.pop());
}
stack.push(c);
continue;
}
if (c == '*' || c == '/') {
while (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/')) {
s1.append(" ").append(stack.pop());
}
stack.push(c);
continue;
}
if (i != 0 && !Character.isDigit(s.charAt(i - 1))) {
s1.append(" ").append(c);
} else {
s1.append(c);
}
}
while (!stack.isEmpty()) {
s1.append(" ").append(stack.pop());
}
return s1.toString();
}
/**
* 后缀表达式求值
*/
public static int suffixValue(String str) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (Character.isDigit(c)) {
int j = i;
while (Character.isDigit(str.charAt(i))) {
i++;
}
stack.push(Integer.valueOf(str.substring(j, i)));
continue;
}
if (c == ' ') {
continue;
}
int b = stack.pop();
int a = stack.pop();
if (c == '*') {
stack.push(a * b);
} else if (c == '/') {
stack.push(a / b);
} else if (c == '+') {
stack.push(a + b);
} else {
stack.push(a - b);
}
}
return stack.pop();
}
}
发表于 2023-08-16 11:06:26
回复(0)
问题信息
难度：
65条回答
2644收藏
10729浏览
通过挑战的用户
查看代码-
2022-09-16 16:05:14
-
2022-09-16 15:14:19
-
2022-09-16 15:06:25
-
2022-09-16 13:45:22 -
2022-09-16 11:57:24
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
