978. Basic Calculator
https://www.lintcode.com/problem/basic-calculator/description
public class Solution {
/**
* @param s: the given expression
* @return: the result of expression
*/
public int calculate(String s) {
// Write your code here
Stack<Integer> stack = new Stack<Integer>();
int result =0;
int number =0;
int sign =1;
for(int i =0;i<s.length();i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
number = 10*number + (int)(c-'0');
}else if(c=='+'){
result +=sign*number;
number =0;
sign =1;
}else if(c == '-'){
result += sign * number;
number = 0;
sign = -1;
}else if(c == '('){
stack.push(result);
stack.push(sign);
sign = 1;
result = 0;
}else if(c == ')'){
result += sign* number;
number =0;
result*=stack.pop();
result+=stack.pop();
}
}
if(number!=0){
result +=sign*number;
}
return result;
}
}
980. Basic Calculator II
https://www.lintcode.com/problem/basic-calculator-ii/description
public class Solution {
/**
* @param s: the given expression
* @return: the result of expression
*/
public int calculate(String s) {
// Write your code here
if(s==null || s.length()==0){
return 0;
}
int len = s.length();
Stack<Integer> stack = new Stack<Integer>();
int num =0;
char sign = '+';
for(int i =0;i<len;i++){
if(Character.isDigit(s.charAt(i))){
num = num*10 + s.charAt(i)-'0';
}
if((!Character.isDigit(s.charAt(i)) && ' '!=s.charAt(i)) ||i==len-1){
if(sign =='-'){
stack.push(-num);
}
if(sign == '+'){
stack.push(num);
}
if(sign == '*'){
stack.push(stack.pop()*num);
}
if(sign == '/'){
stack.push(stack.pop()/num);
}
sign = s.charAt(i);
num =0;
}
}
int re =0;
for(int i:stack){
re +=i;
}
return re;
}
}
849. Basic Calculator III
https://www.lintcode.com/problem/basic-calculator-iii/description
public class Solution {
/**
* @param s: the expression string
* @return: the answer
*/
public int calculate(String s) {
// Write your code here
if(s==null || s.length()==0){
return 0;
}
Stack<Integer> nums = new Stack<Integer>();
Stack<Character> opr = new Stack<Character>();
int num =0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c==' '){
continue;
}
if(Character.isDigit(c)){
num = c-'0';
while(i<s.length()-1 && Character.isDigit(s.charAt(i+1))){
num = num*10+ (s.charAt(i+1)-'0');
i++;
}
nums.push(num);
num =0;
}else if(c=='('){
opr.push(c);
}else if(c==')'){
while(opr.peek()!='('){
nums.push(calculate(nums.pop(),nums.pop(),opr.pop()));
}
opr.pop();
}else if(c=='+'||c=='-'||c=='*'||c=='/'){
if(!opr.isEmpty()&&needCalFirst(opr.peek(),c)){
nums.push(calculate(nums.pop(),nums.pop(),opr.pop()));
}
opr.push(c);
}
}
while(!opr.isEmpty()){
nums.push(calculate(nums.pop(),nums.pop(),opr.pop()));
}
return nums.pop();
}
public int calculate(int num1, int num2, char op){
switch(op){
case '+':return num2+num1;
case '-':return num2-num1;
case '*':return num2*num1;
case '/':return num2/num1;
default:return 0;
}
}
public boolean needCalFirst(char firstOp, char secondOp){
if(firstOp=='('|| firstOp==')'){
return false;
}
if((firstOp=='+'||firstOp=='-')&&(secondOp=='*'||secondOp=='/')){
return false;
}
return true;
}
}
368. Expression Evaluation
https://www.lintcode.com/problem/expression-evaluation/description?_from=ladder&&fromId=4
同849 只需注意输入可能不是一个可计算表达式 eg：{'(',')'}
public class Solution {
/**
* @param expression: a list of strings
* @return: an integer
*/
public int evaluateExpression(String[] expression) {
// write your code here
if(expression==null || expression.length==0){
return 0;
}
String s = "";
for(int i=0;i<expression.length;i++){
s+=expression[i];
}
Stack<Integer> nums = new Stack<Integer>();
Stack<Character> opr = new Stack<Character>();
int num =0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c==' '){
continue;
}
if(Character.isDigit(c)){
num = c-'0';
while(i<s.length()-1 && Character.isDigit(s.charAt(i+1))){
num = num*10+ (s.charAt(i+1)-'0');
i++;
}
nums.push(num);
num =0;
}else if(c=='('){
opr.push(c);
}else if(c==')'){
while(opr.peek()!='('){
if(nums.size()>=2)
nums.push(calculate(nums.pop(),nums.pop(),opr.pop()));
}
opr.pop();
}else if(c=='+'||c=='-'||c=='*'||c=='/'){
if(!opr.isEmpty()&&needCalFirst(opr.peek(),c)){
if(nums.size()>=2)
nums.push(calculate(nums.pop(),nums.pop(),opr.pop()));
}
opr.push(c);
}
}
while(!opr.isEmpty()){
if(nums.size()>=2)
nums.push(calculate(nums.pop(),nums.pop(),opr.pop()));
}
if(nums.size()>0){
return nums.pop();
}
return 0;
}
public int calculate(int num1, int num2, char op){
switch(op){
case '+':return num2+num1;
case '-':return num2-num1;
case '*':return num2*num1;
case '/':return num2/num1;
default:return 0;
}
}
public boolean needCalFirst(char firstOp, char secondOp){
if(firstOp=='('|| firstOp==')'){
return false;
}
if((firstOp=='+'||firstOp=='-')&&(secondOp=='*'||secondOp=='/')){
return false;
}
return true;
}
}