前缀表达式（Polishexpression）前缀表达式也叫波兰表达式，前缀表达式的运算符位于运算符之前，如(3+4)*5-6对应的前缀表达式为-*+3456计算机前缀表达式的计算从右到左扫描表达式。当遇到一个数字时，它被压入堆栈。当遇到运算符时，将栈顶的两个数出栈，用运算符（栈顶元素和次顶元素）对它们进行相应的计算，并将结果压入栈中；重复上述过程，直到表达式的最左端，最后运算得到的值就是表达式的结果。例如：(3+4)*5-6对应前缀表达式为-*+3456前缀表达式的求值步骤如下：从右向左扫描，推6,5,4,3入栈。遇到+运算符，出栈3和4（3为栈顶元素，4为第二个栈顶元素），计算3+4的值，得到7，再将7压入栈中。接下来是*操作符，所以弹出7和5，计算出35，将35压入栈中。最后是-运算符，计算出35-6的值，即29，从而得到最终的结果。中缀表达式是常用的运算表达式，如(3*4)+5-6。中缀表达式的求值是我们最熟悉的，但计算机操作起来并不容易。因此，在计算结果时，往往会将中缀表达式转换成其他表达式进行运算（一般转换成后缀表达式）。后缀表达式也称为反向波兰表达式，它类似于前缀表达式，只是运算符在操作数之后。例如，(3+4)*5-6对应的后缀表达式为34+5*6-再比如，后缀表达式的计算机求值是从左到右扫描表达式。当遇到一个数字时，该数字被压入堆栈。当遇到运算符时，将栈顶的两个元素出栈，使用运算符对它们（栈顶元素和次顶元素）进行相应的计算，并将结果压入栈中，重复上述过程，直到表示最右端，运算得到的最终值就是表达式的结果。例如：(3+4)*5-6对应的后缀表达式为34+5*6-，后缀表达式的求值步骤如下：从左向右扫描，将3和4压入堆。遇到+运算符，弹出4和3（4为栈顶元素，3为第二个栈顶元素），计算7，然后将7压入栈中。将5放入堆栈。遇到*操作符，所以挑出5和7，计算出35，把35压入栈中。6被压入堆栈。最后是-运算符，计算29，得到最终结果。中缀表达式转为后缀表达式1。初始化两个栈：运算符栈s1和存储空间的中间结果栈s2.2。从左到右扫描表达式。3.遇到操作数，压入s2.4。遇到运算符时，与s1栈顶运算符的优先级进行比较等级。如果s1为空，或者栈顶运算符是左括号“(”，则直接将该运算符压入栈中。否则，如果优先级高于栈顶运算符，将运算符压入s1。否则，将s1栈顶运算符弹出压入s2，再次转到(4.1)与s1中新的栈顶运算符进行比较。5.遇到括号时：如果是是左括号“(”，则直接Push入s1。如果是右括号“)”，s1栈顶的运算符将依次出栈，并压入s2，直到遇到左括号，并且此时一对括号将被舍弃。6.重复步骤2~5，直到表达式的最右边。7.将s1中剩余的运算符弹出并压入s2.8中，将其中的元素弹出s2，依次输出，结果倒序就是中缀表达式对应的后缀表达式，简单的postfix表达式计算器packagecom.structures.stack;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;importjava.util.Stack;publicclassPolandNotation{publicstaticvoidmain(String[]args){//给出第一个反波兰表达式(3+4)*5-6==>34+5*6-Stringexpression="1+(((2+3)*4))-5";ListtoInfixExpressionList=toInfixExpressionList(expression);System.out.println(toInfixExpressionList);ListsuffixExpressList=parseSuffixExpressList(toInfixExpressionList);System.out.println(suffixExpressList);System.out.println(calculate(suffixExpressList));/*[1,+,(,(,(,2,+,3,),*,4,),)),-,5]不存在运算符不存在运算符[1,2,3,+,4,*,+,5,-]16*/}//将中缀表达式对应的List转为后缀表达式对应ListpublicstaticListparseSuffixExpressList(Listls){//两个栈的定义Stacks1=newStack<>();//符号栈//说明：因为s2的栈，在整个转换process中，没有pop操作，后面需要进行逆序操作。//所以比较麻烦，这里我们不使用Stack，直接使用Lists2。//Stacks2=newStack<>();//存放中间结果的栈s2Lists2=newArrayList<>();for(Stringitem:ls){if(item.matches("\\d+")){s2.add(item);}elseif(item.equals("(")){s1.push("(");}elseif(item.equals(")")){//如果是右括号")",s1栈顶的运算符依次出栈，压入s2，直到遇到左括号，舍弃这对括号。while(!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();}else{//当item的优先级小于或等于栈顶运算符，将s1栈顶运算符弹出并压入s2，然后转到(4.1)和s1中的新栈顶运算符comparison.while(s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)){s2.add(s1.pop());}//需要将item压入栈中s1.push(item);}}//将s1中剩余的操作符弹出并压入s2while(s1.size()!=0){s2.add(s1.pop());}returns2;}//传递中缀表达式toListpublicstaticListtoInfixExpressionList(Strings){Listls=newArrayList<>();inti=0;Stringstr;//多位拼接charc;do{//如果c为非数，直接加上lsif((c=s.charAt(i))<48||(c=s.charAt(i))<57){ls.add(""+c);i++;}else{//如果是数字，则需要考虑更多的数字问题.str="";while(i=48&&(c=s.charAt(i))<=57){str+=c;i++;}}}while(ils){Stackstack=newStack<>();for(Stringitem:ls){//这里使用正则表达式提取数字，匹配多位数if(item.matches("\\d+")){stack.push(item);}else{intnum2=Integer.parseInt(stack.pop());intnum1=Integer.parseInt(stack.pop());intres=0;switch(item){case"+":res=num1+num2;break;case"-":res=num1-num2;break;case"*":res=num1*num2;break;case"/":res=num1/num2;break;default:thrownewRuntimeException("操作错误");}堆栈。push(res+"");}}returnInteger.parseInt(stack.pop());}}//根据算子返回对应的优先级数classOp生成{privatestaticintADD=1;privatestaticintSUB=1;privatestaticintMUL=2;privatestaticintDIV=2;publicstaticintgetValue(Stringoperation){intresult=0;switch(operation){case"+":result=ADD;break;case"-":result=SUB;break;case"*":result=MUL;break;case"/":result=DIV;break;default:System.out.println("操作符不存在");break;}returnresult;}}【小编推荐】5分钟让你理解K8S必备架构和网络模型的概念。1992年百度程序员被捕，我们有什么警示？开源云盘工具：Nextcloud21私有云盘构建更纯粹，微软Windows1021H2大更新将减少系统臃肿软件数量996操作系统是好是坏？
