给定一个字符串形式的表达式 s ,请你实现一个计算器并返回结果,除法向下取整。
数据范围:表达式长度满足 ,字符串中包含 + , - , * , / , 保证表达式合法。
"1*10"
10
"8*9-19"
53
"100000*100*0"
0
"100000*100/9"
1111111
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ private HashMap<String, Integer> operation = new HashMap<>(); // 运算符优先级 public int calculate (String s) { operation.put("+", 1); operation.put("-", 1); operation.put("*", 2); operation.put("/", 2); // 先得到逆波兰表达式 LinkedList<String> rpn = parseSuffixExpressionList(toInfixExpressionList(s)); // 逆波兰表达式求值 return evalRPN(rpn); } private List<String> toInfixExpressionList(String express){ List<String> list = new ArrayList<>(); int n = express.length(); int num = 0; for(int i = 0; i < n; i++){ char c = express.charAt(i); if(c < '0' || c > '9'){ list.add(String.valueOf(c)); }else{ num = 10 * num + (c - '0'); if(i == n - 1 || (express.charAt(i + 1) < '0' || express.charAt(i + 1) > '9')){ list.add(String.valueOf(num)); num = 0; } } } return list; } private LinkedList<String> parseSuffixExpressionList(List<String> infixExpressionList){ Stack<String> stack = new Stack<>(); LinkedList<String> list = new LinkedList<>(); for(String item: infixExpressionList){ // 当item为数字时,直接加入集合 if(isDigit(item)){ list.add(item); }else if(item.equals("(")){ // 当item为 ( 左括号时,压入栈中 stack.push(item); }else if(item.equals(")")){ // 当item为右括号时,则依次弹出stack栈顶的运算符,并加入list中,直到遇到左括号为止,此时将这一对括号丢弃 while(!stack.peek().equals("(")){ list.add(stack.pop()); } stack.pop(); // 将左括号丢弃 }else{ // 当遇到运算符时 while(!stack.isEmpty() && operation.get(item) <= operation.get(stack.peek())){ list.add(stack.pop()); } stack.push(item); } } // 将stack中的元素全部加入到list中 while(stack.size() > 0){ list.add(stack.pop()); } return list; } // 计算逆波兰表达式 private int evalRPN (LinkedList<String> tokens) { Stack<Integer> stack = new Stack<>(); while(!tokens.isEmpty()) { String token = tokens.removeFirst(); if(isDigit(token)){ stack.push(Integer.parseInt(token)); }else{ int num1 = 0, num2 = 0; if(stack.size() == 1) { return stack.pop(); }else{ num2 = stack.pop(); num1 = stack.pop(); } if(token.equals("+")){ stack.push(num1 + num2); }else if(token.equals("-")){ stack.push(num1 - num2); }else if(token.equals("*")){ stack.push(num1 * num2); }else if(token.equals("/")){ stack.push(num1 / num2); } } } return stack.pop(); } // 判断s是否是数字 private boolean isDigit(String s) { try{ Integer.parseInt(s); return true; }catch(Exception e) { return false; } } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ public int calculate (String s) { // write code here Deque<Integer> stack = new ArrayDeque<>(); char ops = '+'; int num = 0; for(int i = 0; i < s.length(); i++) { if(s.charAt(i) <= '9' && s.charAt(i) >= '0') { num = num * 10 + s.charAt(i) - '0'; if(i != s.length() - 1) continue; } switch(ops) { case '+': stack.offerLast(num); break; case '-': stack.offerLast(-num); break; case '*': stack.offerLast(stack.pollLast() * num); break; case '/': stack.offerLast(stack.pollLast() / num); break; } num = 0; ops = s.charAt(i); } int res = 0; while(!stack.isEmpty()) { res += stack.pollLast(); } return res; } }NC137、NC240、NC241可以看作是同一题,一个解法通吃
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ public int calculate (String s) { // write code here Stack<String> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) < '0' || s.charAt(i) > '9') { stack.push(s.substring(i, i + 1)); continue; } int j = i; while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') { j++; } int num1 = Integer.parseInt(s.substring(i, j)); i = j - 1; if (!stack.isEmpty()) { if (stack.peek().equals("*")) { stack.pop(); int num2 = Integer.parseInt(stack.pop()); stack.push(String.valueOf(num2 * num1)); } else if (stack.peek().equals("/")) { stack.pop(); int num2 = Integer.parseInt(stack.pop()); stack.push(String.valueOf(num2 / num1)); } else stack.push(String.valueOf(num1)); } else stack.push(String.valueOf(num1)); } while (true) { int num1 = Integer.parseInt(stack.pop()); if (stack.isEmpty()) { return num1; } String op = stack.pop(); int num2 = Integer.parseInt(stack.pop()); if (op.equals("+")) { stack.push(String.valueOf(num2 + num1)); } if (op.equals("-")) { stack.push(String.valueOf(num2 - num1)); } } } }
package main import _"fmt" import "strconv" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ func calculate( s string ) int { ints:=[]int{} symbols:=[]byte{} pre:="" for _,ch:=range []byte(s){ if ch=='-'||ch=='+'{ ints=append(ints,calc(pre)) symbols=append(symbols,ch) pre="" }else{ pre+=string(ch) } } ints=append(ints,calc(pre)) ans:=ints[0] for i,x:=range ints[1:]{ if symbols[i]=='-'{ ans-=x }else{ ans+=x } } return ans } func calc(s string)int{ ints:=[]int{} symbols:=[]byte{} pre:="" for _,ch:=range []byte(s){ if ch=='*'||ch=='/'{ x,_:=strconv.Atoi(pre) ints=append(ints,x) symbols=append(symbols,ch) pre="" }else{ pre+=string(ch) } } x,_:=strconv.Atoi(pre) ints=append(ints,x) ans:=ints[0] for i,x:=range ints[1:]{ if symbols[i]=='*'{ ans*=x }else{ ans/=x } } return ans }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ int calculate(string s) { // write code here s += '&'; stack<int> number1; stack<char> operation; int i =0; int flag = 0; int tmp =0; while(i<s.length()) { if(s[i] <= '9' && s[i] >= '0') { tmp = tmp * 10 + s[i] - '0'; } else { number1.push(tmp); tmp = 0; if(flag == 1) { int num1 = number1.top(); number1.pop(); int num2 = number1.top(); number1.pop(); char opra = operation.top(); operation.pop(); if(opra == '*') number1.push(num1 * num2); else if(opra == '/') number1.push(num2 / num1); flag = 0; } if(s[i] == '+' || s[i] == '-' || s[i] == '&') { while(!operation.empty()) { int num1 = number1.top(); number1.pop(); int num2 = number1.top(); number1.pop(); char opera = operation.top(); operation.pop(); if(opera == '+') number1.push(num2+num1); else if(opera == '-') number1.push(num2-num1); else if(opera == '*') number1.push(num2 * num1); else if(opera == '/') number1.push(num2/num1); } } else flag = 1; operation.push(s[i]); } i++; } return number1.top(); } };