给你一个字符串，这个字符串表示一个表达式，这个表达式可能有整数，加减乘除符号和小括号，求这个表达式的值。
算法步骤&原理
- 首先假如只有加减符号，并且都是整数，那么很容易求解，遍历一遍即可getNum实现。
- 现在再加入乘除。在遍历表达式的时候，开始的数字加到队列中，然后符号加到队列中，然后后边遇到数字的时候，首先看队列中的那个符号是不是加减，加减的话直接把这个数加进去，否则需要与队列里面的数和那个符号计算之后再加进去。
- 上面的描述可以解决有加减乘除的情况，如果在假如括号的话，就是首先计算各个括号里面的值，计算结果加到队列当中，然后再计算所有的。
public static int getValue(String str) {
return value(str.toCharArray(), 0)[0];//返回表达式的值
}
public static int[] value(char[] str, int i) {
LinkedList<String> que = new LinkedList<String>();
int pre = 0;
int[] bra = null;
while (i < str.length && str[i] != ')') {//以一个括号包含的数为单位进行计算
if (str[i] >= '0' && str[i] <= '9') {//遇到了数字
pre = pre * 10 + str[i++] - '0';
} else if (str[i] != '(') {//遇到了+ - * /
addNum(que, pre);//处理之前的数，直接加到队列中或者与队列中原有的操作符和数字结合之后再加进去
que.addLast(String.valueOf(str[i++]));//队列中加入运算符号
pre = 0;
} else {//遇到了左括号
bra = value(str, i + 1);//计算这个括号内的值
pre = bra[0];//括号能的值
i = bra[1] + 1;//右括号的下一个位置，也就是下一次计算的开始位置
}
}
addNum(que, pre);//最后一个数加到队列当中
return new int[] { getNum(que), i };//返回一个“部分”的值和计算到的位置
}
public static void addNum(LinkedList<String> que, int num) {
if (!que.isEmpty()) {//队列为null,证明此时还没有数加进来，进来的num是第一个数，直接加到队列中即可
int cur = 0;
String top = que.pollLast();
if (top.equals("+") || top.equals("-")) {//队列首部为加或者减，不做操作，弹出的继续加回去
que.addLast(top);
} else {//队列首部为/或者*，需要与进来的数结合后再重新加入队列中
cur = Integer.valueOf(que.pollLast());
num = top.equals("*") ? (cur * num) : (cur / num);
}
}
que.addLast(String.valueOf(num));
}
public static int getNum(LinkedList<String> que) {//只有加减时的运算3+4-5+6
int res = 0;
boolean add = true;
String cur = null;
int num = 0;
while (!que.isEmpty()) {
cur = que.pollFirst();
if (cur.equals("+")) {
add = true;
} else if (cur.equals("-")) {
add = false;
} else {
num = Integer.valueOf(cur);
res += add ? num : (-num);
}
}
return res;
}
[没有括号leetcode227]https://leetcode.com/problems/basic-calculator-ii/
public class Solution {
public int calculate(String s) {
return value(s.toCharArray());
}
public int value(char[] str){
LinkedList<String> list=new LinkedList<String>();
int i=0;
int pre=0;
while(i<str.length){
if(str[i]==' '){
i++;
continue;
}
else if(str[i]>='0'&&str[i]<='9'){
pre=pre*10+str[i++]-'0';
}
else{
addNum(list,pre);
list.addLast(String.valueOf(str[i++]));
pre=0;
}
}
addNum(list,pre);
return getNum(list);
}
public void addNum(LinkedList<String> list,int num){
if(!list.isEmpty()){
String flag=list.pollLast();
if(flag.equals("+")||flag.equals("-"))
list.addLast(flag);
else{
int pre=Integer.valueOf(list.pollLast());
num=flag.equals("*")?pre*num:pre/num;
}
}
list.addLast(String.valueOf(num));
}
public int getNum(LinkedList<String> list){
int res=0;
boolean add=true;
String cur=null;
int num=0;
while(!list.isEmpty()){
cur=list.pollFirst();
if(cur.equals("+"))
add=true;
else if(cur.equals("-")){
add=false;
}
else{
num=Integer.valueOf(cur);
res=(add?res+num:res-num);
}
}
return res;
}
}
[有括号没乘除leetcode224]https://leetcode.com/problems/basic-calculator/
public class Solution {
public int calculate(String s) {
return value(s.toCharArray(),0)[0];
}
public int[] value(char[] str,int i){
int[] bra=new int[2];
boolean add=true;
int res=0;
int pre=0;
while(i<str.length&&str[i]!=')'){
if(str[i]==' '){
i++;
}
else if(str[i]>='0'&&str[i]<='9'){
pre=pre*10+str[i++]-'0';
}
else if(str[i]!='('){
if(add)
res+=pre;
else
res-=pre;
pre=0;
add=str[i++]=='+'?true:false;
}else{
bra=value(str,i+1);
pre=bra[0];
i=bra[1]+1;
}
}
if(add)
res+=pre;
else
res-=pre;
bra[0]=res;
bra[1]=i;
return bra;
}
}
