表达式求值

求解代码

HashMap<Character,Integer>map=newHashMap<Character,Integer>(){{put('+',1);put('-',1);put('*',2);}};voidcalc(LinkedList<Integer>nums,LinkedList<Character>operators){if(nums.isEmpty()||nums.size()<2){return;}if(operators.isEmpty()){return;}intb=nums.pollLast();inta=nums.pollLast();charoperator=operators.pollLast();intres=0;if(operator=='+'){res=a+b;}elseif(operator=='-'){res=a-b;}elseif(operator=='*'){res=a*b;}nums.addLast(res);}publicintsolve(Strings){s=s.replaceAll(" ","");char[]str=s.toCharArray();intn=s.length();LinkedList<Integer>nums=newLinkedList<>();LinkedList<Character>operators=newLinkedList<>();nums.addLast(0);for(inti=0;i<n;i++){charc=str[i];if(c=='('){operators.addLast(c);}elseif(c==')'){while(!operators.isEmpty()){if(operators.peekLast()!='('){calc(nums,operators);}else{operators.pollLast();break;}}}else{if(Character.isDigit(c)){intbase=0;intj=i;while(j<n&&Character.isDigit(str[j])){base=base*10+(str[j++]-'0');}nums.addLast(base);i=j-1;}else{if(i>0&&(str[i-1]=='('||str[i-1]=='+'||str[i-1]=='-')){nums.addLast(0);}while(!operators.isEmpty()&&operators.peekLast()!='('){charprev=operators.peekLast();if(map.get(prev)>=map.get(c)){calc(nums,operators);}else{break;}}operators.addLast(c);}}}while(!operators.isEmpty()&&operators.peekLast()!='('){calc(nums,operators);}returnnums.peekLast();}

小贴士

1.nums.addLast(0)主要用于处理【表达式以正负号开头】的场景，比如-1+2、+3*4，可以把-1转为0-1，把+3转为0+3

2.i = j - 1可以修正外层for循环的索引i，让i直接跳到「当前多位数的最后一位」，抵消for循环的自动i++，避免重复遍历已经处理过的数字字符。、

比如表达式123+4，j=3：

执行i = j - 1 → i = 3 - 1 = 2，然后，外层for循环执行自动i++ → i从2变成3，下一轮循环，i=3，正好读取字符str[3] → '+'。