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);}