1.棧的應用

后入先出的有序列表

	//無法進行小數、負數計算，除法計算為在除法步驟時舍棄小數部分public static void main(String[] args) {//雙棧實現計算器功能,思路//1.定義數棧1、符號棧2、掃描指針index，從前往后掃描表達式序列//2.遇到數字，保存到list中，直到掃描到符號，將數字還原成多位數，壓入棧1//3遇到符號，分以下情況//3.1如果為左括號，直接入棧//3.2如果為右括號，依次彈出棧2的一個符號和// 棧1的兩個數字計算，將結果壓入棧1，直到彈出左括號//3.3如果為運算符且棧2為空，壓入棧2，//3.4如果運算符優先級小于或等于棧2棧頂符號，彈出棧2棧頂符號和棧1兩個數字計算//3.5如果運算符優先級大于棧2棧頂符號，壓入棧2//4.掃描結束，依次彈出棧2的一個符號和// 棧1的兩個數字計算，將結果壓入棧1，最終棧1數字為運算結果
//        String string = "5+2*3-4";
//        String string = "10+20*3-40/2";
//        String string = "100+200/50*3";String string ="10*(2+3)-40/2";ArrayDeque<Integer> numStack = new ArrayDeque<>();//數棧ArrayDeque<Character> strStack = new ArrayDeque<>();//符號棧int index=0;//掃描指針while (index<string.length()){char c=string.charAt(index);if(Character.isDigit(c)){//步驟2int num=0;//存儲多位數數值//計算多位數while (index<string.length()&&Character.isDigit(string.charAt(index))){num=num*10+(string.charAt(index)-'0');index++;}numStack.push(num);//將數字壓入數棧continue;}if(c=='+'||c=='-'||c=='*'||c=='/'){//3.2和3.5if(strStack.isEmpty() || hasPrecedence(c,strStack.peek())){strStack.push(c);}else {//3.4calculateTop(numStack,strStack);strStack.push(c);}}else if(c=='('){//3.1strStack.push(c);}else if(c==')'){//3.2while (strStack.peek()!='('){calculateTop(numStack,strStack);}strStack.pop();}index++;}while (!strStack.isEmpty()){//步驟4calculateTop(numStack,strStack);}System.out.println("最終結果為："+numStack.poll());}//判斷優先級，true為a比b的優先級高public static boolean hasPrecedence(char a,char b){if((a=='*'||a=='/')&&(b=='+'||b=='-')){return true;}if(b=='('){return true;}return false;}//計算棧頂元素public static void calculateTop(ArrayDeque<Integer> numStack,ArrayDeque<Character> strStack){int num1=numStack.pop();int num2=numStack.pop();char op=strStack.pop();int temp=0;switch (op){case '+':temp=num2+num1;break;case '-':temp=num2-num1;break;case '*':temp=num2*num1;break;case '/':temp=num2/num1;break;}numStack.push(temp);}