请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：
，保证计算结果始终在整型范围内
要求：空间复杂度： )
，时间复杂度
[编程题]表达式求值
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)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
// write code here
Map<Character,Integer> map = new HashMap<Character,Integer> ();
map.put('+',1);
map.put('-',1);
map.put('*',2);
Stack<Integer> nums = new Stack<Integer>();
Stack<Character> ops = new Stack<Character>();
int num = s.length();
char[] ss = s.toCharArray();
for (int i = 0 ; i < num; i++) {
char ch = ss[i];
if (isNumber(ch)) {
int temp = 0;
int j = i;
while (j < num && isNumber(ss[j])) {
temp = temp * 10 + (ss[j] - '0');
j++;
}
nums.push(temp);
i = j - 1;
} else if (ch == '(') {
ops.push(ch);
}else if(ch==')'){
while(ops.peek()!='('){
calcu(nums,ops);
}
ops.pop();
}else{
while(!ops.isEmpty()&&ops.peek()!='('&&(map.get(ops.peek())>=map.get(ch))){
calcu(nums,ops);
}
ops.push(ch);
}
}
while(!ops.isEmpty()){
calcu(nums,ops);
}
return nums.pop();
}
public boolean isNumber (char a) {
return Character.isDigit(a);
}
public void calcu (Stack<Integer> nums, Stack<Character> ops) {
int num1 = nums.pop();
int num2 = nums.pop();
char op = ops.pop();
if (op == '+') {
nums.push(num1 + num2);
} else if (op == '-') {
nums.push(num2 - num1) ;
} else if (op == '*') {
nums.push(num1 * num2);
}
}
}
发表于 2023-08-13 21:41:22
回复(0)
import java.util.*;
/*
op1->+|-,
op2->*|/,
exp->term[op1 term]*,
term->factor[op2 factor]*,
factor->number|(exp),
首先改造文法为:
exp->term exp1,
exp1->op1 term exp1,
exp1->null,
term->factor term1,
term1->op2 factor term1,
term1->null,
factor->number|(exp),
follow(term1)=follow(term),
first(exp1)={op1,null} subset of follow(term),
由于first(exp1)包含null,因此,follow还必须包含follow(exp1),
follow(exp1)=follow(exp)={)},
故follow(term1)={op1,),null},
*/
enum NodeType {
NUMBER,
OPERATOR,
}
class Node {
String word;
NodeType nodeType;
Node left;
Node right;
public Node() {
}
public Node(String word, NodeType nodeType) {
this.word = word;
this.nodeType = nodeType;
}
public static Node getOperatorNode(String word) {
Node node = new Node();
node.word = word;
node.nodeType = NodeType.OPERATOR;
return node;
}
public static Node getNumberNode(String word) {
Node node = new Node();
node.word = word;
node.nodeType = NodeType.NUMBER;
return node;
}
public boolean isOp1(){
return word.equals("+")||word.equals("-");
}
public boolean isOp2(){
return word.equals("*")||word.equals("/");
}
}
class WordReader {
String resource;
int nextCharIndex = 0;
int left = 0;
int right = 0;
public WordReader(String s) {
resource = s;
right = resource.length() - 1;
}
public WordReader(String s, int left, int right) {
resource = s;
this.left = left;
this.right = right;
}
public boolean hasNextWord() {
return right >= nextCharIndex;
}
public char nextChar() {
char c = resource.charAt(nextCharIndex);
nextCharIndex++;
return c;
}
public char lookAhead() {
char c = resource.charAt(nextCharIndex);
return c;
}
public String readNumber() {
StringBuilder sb = new StringBuilder();
while (nextCharIndex < resource.length()) {
char c = resource.charAt(nextCharIndex);
if (c <= '9' && c >= '0') {
sb.append(c);
nextCharIndex++;
} else {
break;
}
}
return sb.toString();
}
public String readNextChar() {
char c = resource.charAt(nextCharIndex);
nextCharIndex++;
return new String(new char[] {c});
}
public Node readNextWord() {
char c = lookAhead();
String word = null;
if (c <= '9' && c >= '0') {
word = readNumber();
return Node.getNumberNode(word);
} else {
word = readNextChar();
return Node.getOperatorNode(word);
}
}
public void readBack(Node node) {
nextCharIndex -= node.word.length();
}
}
class Parser {
WordReader wordReader;
public Parser(String s) {
wordReader = new WordReader(s);
}
public Node parse() {
return exp();
}
//exp->term exp1,只有一个推导式,因此只能使用它
public Node exp() {
return exp1(term());
}
//exp1->op1 term exp1,
//exp1->null,
public Node exp1(Node prev) {
if (wordReader.hasNextWord()) {
Node n1 = wordReader.readNextWord();
if (n1.isOp1()) {
//选择exp1->op1 term exp1
n1.left = prev;
n1.right = term();
return exp1(n1);
} else if (n1.word.equals(")")) {
//follow(exp1)={)},
wordReader.readBack(n1);
return prev;
}
}
return prev;
}
//term->factor term1,
public Node term() {
return term1(factor());
}
//term1->op2 factor term1,
//term1->null,
//由于term1的推导式当中涉及到操作符,因此,需要将之前已经形成的ast传入作为操作数的左节点
public Node term1(Node prev) {
if (wordReader.hasNextWord()) {
Node n1 = wordReader.readNextWord();
if (n1.isOp2()) {
//选择term1->op2 factor term1
n1.left = prev;
n1.right = factor();
return term1(n1);
} else if (n1.isOp1() || n1.word.equals(")")) {
//当n1 in follow(term1)时,说明需要选用term1->null
//follow(term1)={op1,),null}
wordReader.readBack(n1);
return prev;
}
}
return prev;
}
//factor->number|(exp)
public Node factor() {
if (wordReader.hasNextWord()) {
Node n1 = wordReader.readNextWord();
int t = 0;
if (n1.nodeType.equals(NodeType.NUMBER)) {
//选择factor->number
return n1;
} else if (n1.word.equals("(")) {
//选择factor->(expression)
Node n2 = exp();
if (wordReader.hasNextWord() && wordReader.readNextWord().word.equals(")")) {
return n2;
}
}
}
return null;
}
}
public class Solution {
public int calculate(Node root) {
if (root == null) {
return 0;
}
if (root.nodeType.equals(NodeType.NUMBER)) {
return Integer.parseInt(root.word);
}
int x = calculate(root.left);
int y = calculate(root.right);
char op = root.word.charAt(0);
switch (op) {
case '+':
return x + y;
case '-':
return x - y;
case '*':
return x * y;
case '/':
return x / y;
}
return 0;
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
Parser parser = new Parser(s);
Node root = parser.parse();
return calculate(root);
}
}
发表于 2023-05-24 17:10:52
回复(1)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
char[] chars = s.toCharArray();
Stack<Integer> numStack = new Stack<>();//运算数
Stack<Character> operatorStack = new Stack<>();//运算符
for(int i=0;i<chars.length;i++){
char curchar = chars[i];
if(isDight(curchar)){//数字
int num = 0;
while(i<chars.length && isDight(chars[i])){//循环读取当前数字(多位)
num = num*10+(chars[i]-'0');
i++;
}
i--;//将i-1当前指针指向当前数的最后一位
numStack.push(num);//数字入栈
}else if(curchar=='('){//'('入栈
operatorStack.push(curchar);
}else if(curchar==')'){//遇到')'开始运算()内的表达式
while(operatorStack.peek()!='('){//多个()嵌套处理
operate(numStack,operatorStack);
}
operatorStack.pop();// '('出栈
}else {
while(!operatorStack.isEmpty() && getPriority(curchar) <= getPriority(operatorStack.peek()) ){//当前优先级<栈内优先级
operate(numStack,operatorStack);//提取表达式计算
}
operatorStack.push(curchar);//当前运算符入栈
}
}
while(!operatorStack.isEmpty()){//运算符不为空,继续计算
operate(numStack,operatorStack);
}
return numStack.pop();//返回最后结果
}
private int getPriority(Character character) {//优先级
if(character == '+' || character=='-'){
return 1;
}else if(character =='*' || character =='/'){
return 2;
}
return -1;//遇见'()'的优先级
}
private void operate(Stack<Integer> numStack, Stack<Character> operatorStack) {//提取当前表达式计算
char operator = operatorStack.pop();
int rightnum = numStack.pop();
int leftnum = numStack.pop();
int newnum = compute(leftnum,operator,rightnum);//计算
numStack.push(newnum);//添加运算结果入栈
}
private int compute(int a, char operator, int b) {
switch (operator){
case '+': return a + b;
case '-': return a-b;
case '*': return a*b;
case '/':
if(b==0){
throw new RuntimeException("cannot not divide 0!");
}
return a/b;
default :
throw new UnsupportedOperationException();
}
}
private boolean isDight(char curchar) {
return curchar>='0' && curchar <='9';
}
}
发表于 2023-05-15 13:13:18
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve1 (char ch, int a, int b) {
switch (ch) {
case '+':
return b + a;
case '-':
return b - a;
case '*':
return b * a;
}
return 0;
}
public int solve (String s) {
// write code here
Stack<Character> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
char ch;
int i = 0;
String s1 = "";
short flag1 = 0;
short flag2 = 0;
while (i < s.length()) {
ch = s.charAt(i);
if (!stack1.empty() && stack1.peek() == '*'){
flag1 = 1;
}
if ( ch == ')') {
while (stack1.peek() != '(') {
int eg = solve1(stack1.pop(), stack2.pop(), stack2.pop());
stack2.push(eg);
}
stack1.pop();
if (flag1 == 1 && flag2 >0){
flag2--;
}
i++;
} else {
s1 = "";
while (ch != '+' && ch != '*' && ch != '-' && ch != '(' && ch != ')') {
if (i < s.length() - 1) {
s1 += ch;
ch = s.charAt(++i);
} else if (i == s.length() - 1) {
s1 += ch;
i++;
}
if (i == s.length()) {
break;
}
}
if (s1 != "") {
stack2.push(Integer.parseInt(s1));
}
if (flag1 == 1 && ch == '(' ){
flag2++;
}
if (flag1 == 1 && flag2 == 0 && !stack1.empty()){
int eg = solve1(stack1.pop(), stack2.pop(), stack2.pop());
stack2.push(eg);
flag1 = 0;
}
if (ch == '+' || ch == '*' || ch == '(' || ch == '-') {
stack1.push(ch);
i++;
}
}
}
while (!stack1.empty() ) {
char eg1 = stack1.pop();
if (!stack1.empty() && stack1.peek() == '-') {
if (eg1 == '-')
eg1 = '+';
else
eg1 = '-';
}
int eg2 = solve1(eg1, stack2.pop(), stack2.pop());
stack2.push(eg2);
}
return stack2.pop();
}
}
发表于 2023-05-05 11:31:20
回复(0)
import java.util.*;
//最原始的用了两个栈实现， 注意：1.char转int,不能强转，负责会得到字符编码，
2.实现字符出栈还是进栈，用了循环控制，使用了break，发现其在while循环里的位置，很神奇。
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
// write code here
char a[] = s.toCharArray();
stack1 s1 = new stack1();
stack2 s2 = new stack2();
s2.push2(s2, '#');
test03 tt = new test03();
s1 = tt.test(s1, s2, a);
int result = s1.pop1(s1);
return result;
}
public class test03 {
stack1 s1;
stack2 s2;
public int count(int m, int n, char c) {
int result1 = 0;
switch (c) {
case '+':
result1 = m + n;
break;
case '-':
result1 = n - m;
break;
case '*':
result1 = m * n;
break;
case '/':
result1 = n / m;
break;
}
return result1;
}
public boolean isDigit(char c) {
if (Character.isDigit(c))
return true;
else
return false;
}
public int compare(char c1, char c2) {
int flag = 0;
switch (c1) {
case '*':
case '/':
if (c2 == '+' || c2 == '-' || c2 == '*' || c2 == '/' || c2 == ')' || c2 == '#')
flag = 1; //出栈
else if (c2 == '(')
flag = 2; //* /比（小；
break;
case '+':
case '-':
if (c2 == '+' || c2 == '-' || c2 == ')' || c2 == '#')
flag = 1; //比之大
else if (c2 == '*' || c2 == '/' || c2 == '(')
flag = 2;
break;
case '(':
if (c2 == ')')
flag = 3;
else flag = 2;
break;
}
return flag;
}
public stack1 test(stack1 s1, stack2 s2, char a[]) {
for (int i = 0; i < a.length; i++) {
//char c = s.charAt(i);
if (isDigit(a[i])) {
String s = String.valueOf(a[i]);
int t = Integer.parseInt(s);
s1.push1(s1, t);
} else {
char cc = s2.getTop(s2);
if (cc == '#')
s2.push2(s2, a[i]);
else {
while (true) {
if (compare(cc, a[i]) == 2) {
s2.push2(s2, a[i]);
break;
} else if (compare(cc, a[i]) == 1) {
int m = s1.pop1(s1);
int n = s1.pop1(s1);
char ccc = s2.pop2(s2);
if (m != 0 && n != 0 && ccc != '0') {
int resulet = count(m, n, ccc);
//char rs = (char)(resulet+48);
s1.push1(s1, resulet);
cc = s2.getTop(s2);
if (cc == '#') {
s2.push2(s2, a[i]);
break;
}
//break; }
}
} else {
if (compare(cc, a[i]) == 3) {
s2.pop2(s2);
// break;
}
break;
}
// break;
}
}
}
//return s1;
}//当表达式输入完了。
while (s1.isEmpty(s1) && s2.isEmpty(s2)) {
int m1 = s1.pop1(s1);
System.out.println("m1:" + m1);
int m2 = s1.pop1(s1);
System.out.println("m2:" + m2);
char m3 = s2.pop2(s2);
if (m1 != 0 && m2 != 0 && m3 != '0') {
int rs1 = count(m1, m2, m3);
// char rs2 = (char)(rs1+48);
s1.push1(s1, rs1);
}
}
return s1;
}
}
public class stack1 {
int base = 0;
int top = 0;
int a[] = new int[100];
//stack1 s1=new stack1();
public stack1() {
}
public boolean isEmpty(stack1 s1) {
if ( s1.top == s1.base)
return false;
else return true;
}
public int gettop(stack1 s1) {
return s1.a[s1.top - 1];
}
public int push1(stack1 s1, int i) {
// String s=String.valueOf(c);
// int i=Integer.parseInt(s);
s1.a[s1.top] = i;
//System.out.println(i+":"+s1.top);
++s1.top;
return s1.top;
}
public int pop1(stack1 s1) {
if (s1.base == s1.top)
return 0;
int m = s1.a[s1.top - 1];
s1.top--;
return m;
}
}
public class stack2 {
int base = 0;
int top = 0;
char c[] = new char[100];
public stack2() {}
//stack2 s2=new stack2();
public int push2(stack2 s2, char c) {
s2.c[s2.top] = c;
++s2.top;
return s2.top;
}
public char pop2(stack2 s2) {
if (s2.base == s2.top)
return '0';
char m = s2.c[s2.top - 1];
s2.top--;
return m;
}
public char getTop(stack2 s2) {
if (s2.c[s2.top - 1] != '#')
return s2.c[s2.top - 1];
else return '#';
}
public boolean isEmpty(stack2 s2) {
if ( s2.c[s2.top-1]=='#')
return false;
else return true;
}
}
}
发表于 2023-04-24 09:54:55
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
public int solve (String s) {
// write code here
return func(s, 0, s.length() - 1);
}
public int func(String s, int startIndex, int endIndex) {
Stack<Integer> st = new Stack<>();
char op = '+';
for (int i = startIndex; i <= endIndex; i++) {
int num = 0;
boolean isNum = false;
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
isNum = true;
num = s.charAt(i) - '0';
while (i+1 <= endIndex && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '9') {
i++;
num = num * 10 + (s.charAt(i) - '0');
}
}
if (isNum && op == '+') {
st.push(num);
}
else if (isNum && op == '-') {
st.push(0 - num);
}
else if (isNum && op == '*') {
int preNum = st.pop();
st.push(preNum * num);
}
else if (!isNum && s.charAt(i) == '(') {
int leftCount = 0;
int nextStart = i + 1;
i++;
while (i <= s.length() - 1 && (s.charAt(i) != ')' || leftCount != 0)) {
if (s.charAt(i) == '(') {
leftCount++;
}
else if (s.charAt(i) == ')') {
leftCount--;
}
i++;
}
int nextEnd = i - 1;
num = func(s, nextStart, nextEnd);
if (op == '+') {
st.push(num);
}
else if (op == '-') {
st.push(0 - num);
}
else if (op == '*') {
int preNum = st.pop();
st.push(preNum * num);
}
}
else if (!isNum && (s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*')) {
op = s.charAt(i);
}
}
int ans = 0;
while (!st.isEmpty()) {
ans += st.pop();
}
return ans;
}
}
发表于 2023-04-07 11:05:26
回复(0)
问题信息
难度：
59条回答
2221收藏
7685浏览
通过挑战的用户
查看代码-
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号
