赞
踩
实现一个基本的计算器来计算一个简单的字符串表达式。
字符串表达式可以包含左括号 ( ,右括号),加号+ ,减号 -,非负整数和空格 。
假定所给的表达式语句总是正确有效的。
例如:
“1 + 1” = 2
” 2-1 + 2 ” = 3
“(1+(4+5+2)-3)+(6+8)” = 23
思路:
每次遇到左括号、数字、加减号都入栈,遇到右括号出栈,直到弹出对应左括号,对于每次出栈后的子串,进行计算,再将结果重新入栈
class Solution {
public int calculate(String s) {
LinkedList<String> lk = new LinkedList<String>();
for(int i=0;i<s.length();){
if(s.charAt(i) == '('){
lk.push("(");
i++;
}
else if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
String tempNum = "";
while(i<s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9'){
tempNum += s.charAt(i);
i++;
}
lk.push(tempNum);
}
else if(s.charAt(i) == ' '){
i++;
}
else if(s.charAt(i) == '+' || s.charAt(i) == '-'){
lk.push(s.charAt(i) + "");
i++;
}
else{//右括号
String str = lk.pop();
String tempStr = "";
while(!str.equals("(")){//直到左括号
tempStr = str + tempStr;
str = lk.pop();
}
//如果取出来可以运算则运算
String leftSign = "";
String rightSign = "";
if(!"".equals(tempStr) && (tempStr.startsWith("-") || tempStr.startsWith("+"))){
leftSign = tempStr.substring(0,1);
tempStr = tempStr.substring(1);
}
if(!"".equals(tempStr) && (tempStr.endsWith("-") || tempStr.endsWith("+"))){
rightSign = tempStr.charAt(tempStr.length()-1) + "";
tempStr = tempStr.substring(1,tempStr.length()-1);
}
tempStr = cal(tempStr) + "";
if(!"".equals(leftSign)){
lk.push(leftSign);
}
if(!"".equals(tempStr)){
lk.push(tempStr);
}
if(!"".equals(rightSign)){
lk.push(rightSign);
}
i++;
}
}
String temp = "";
while(!lk.isEmpty()){
temp = lk.pop() + temp;
}
return cal(temp);
}
public int cal(String str){
int preNum = 0;
int i=0;
int sign = 1;
if(str.length() != 0 && (str.charAt(0) == '-' || str.charAt(0) == '+')){//第一个数是负数
if(str.charAt(0) == '-'){
sign = -1;
}
i++;
}
while(i< str.length() && str.charAt(i) != '+' && str.charAt(i) != '-'){
preNum *= 10;
preNum += str.charAt(i) - '0';
i++;
}
preNum *= sign;
while(i< str.length()){
if(str.charAt(i) == '+' || str.charAt(i) == '-'){
if(str.charAt(i) == '-'){
sign *= -1;
}
i++;
}
else{
int tempNum = 0;
while(i< str.length() && str.charAt(i) != '+' && str.charAt(i) != '-'){
tempNum *= 10;
tempNum += str.charAt(i) - '0';
i++;
}
if(sign == 1){
preNum = preNum + tempNum;
}
else{
preNum = preNum - tempNum;
}
sign = 1;
}
}
return preNum;
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。