給你一個(gè)字符串漾月，這個(gè)字符串表示一個(gè)表達(dá)式病梢，這個(gè)表達(dá)式可能有整數(shù)，加減乘除符號和小括號，求這個(gè)表達(dá)式的值蜓陌。
算法步驟&原理
- 首先假如只有加減符號觅彰，并且都是整數(shù)，那么很容易求解钮热，遍歷一遍即可getNum實(shí)現(xiàn)填抬。
- 現(xiàn)在再加入乘除。在遍歷表達(dá)式的時(shí)候隧期，開始的數(shù)字加到隊(duì)列中飒责，然后符號加到隊(duì)列中，然后后邊遇到數(shù)字的時(shí)候仆潮，首先看隊(duì)列中的那個(gè)符號是不是加減宏蛉，加減的話直接把這個(gè)數(shù)加進(jìn)去，否則需要與隊(duì)列里面的數(shù)和那個(gè)符號計(jì)算之后再加進(jìn)去性置。
- 上面的描述可以解決有加減乘除的情況檐晕，如果在假如括號的話，就是首先計(jì)算各個(gè)括號里面的值蚌讼，計(jì)算結(jié)果加到隊(duì)列當(dāng)中，然后再計(jì)算所有的个榕。
public static int getValue(String str) {
return value(str.toCharArray(), 0)[0];//返回表達(dá)式的值
}
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] != ')') {//以一個(gè)括號包含的數(shù)為單位進(jìn)行計(jì)算
if (str[i] >= '0' && str[i] <= '9') {//遇到了數(shù)字
pre = pre * 10 + str[i++] - '0';
} else if (str[i] != '(') {//遇到了+ - * /
addNum(que, pre);//處理之前的數(shù)篡石，直接加到隊(duì)列中或者與隊(duì)列中原有的操作符和數(shù)字結(jié)合之后再加進(jìn)去
que.addLast(String.valueOf(str[i++]));//隊(duì)列中加入運(yùn)算符號
pre = 0;
} else {//遇到了左括號
bra = value(str, i + 1);//計(jì)算這個(gè)括號內(nèi)的值
pre = bra[0];//括號能的值
i = bra[1] + 1;//右括號的下一個(gè)位置，也就是下一次計(jì)算的開始位置
}
}
addNum(que, pre);//最后一個(gè)數(shù)加到隊(duì)列當(dāng)中
return new int[] { getNum(que), i };//返回一個(gè)“部分”的值和計(jì)算到的位置
}
public static void addNum(LinkedList<String> que, int num) {
if (!que.isEmpty()) {//隊(duì)列為null,證明此時(shí)還沒有數(shù)加進(jìn)來西采，進(jìn)來的num是第一個(gè)數(shù)凰萨，直接加到隊(duì)列中即可
int cur = 0;
String top = que.pollLast();
if (top.equals("+") || top.equals("-")) {//隊(duì)列首部為加或者減，不做操作械馆，彈出的繼續(xù)加回去
que.addLast(top);
} else {//隊(duì)列首部為/或者*胖眷，需要與進(jìn)來的數(shù)結(jié)合后再重新加入隊(duì)列中
cur = Integer.valueOf(que.pollLast());
num = top.equals("*") ? (cur * num) : (cur / num);
}
}
que.addLast(String.valueOf(num));
}
public static int getNum(LinkedList<String> que) {//只有加減時(shí)的運(yùn)算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;
}
}
