前缀表达式的计算机求值

前缀表达式的计算机求值特点

引例：某表达式的前缀形式为”+ -*^ABCD/E/F+GH”,那么它的中缀形式为？

前缀表达式的操作

计算过程：题目中前缀形式为：±*^ABCD/E/F+GH

1. 首先扫描 H,是数字 入栈 ，栈中为: H
   2)扫描 G 为数字 入栈 ,栈中为:G,H
   3)扫描+ 为运算符 ,依次弹出G ,H ,得到 G+H 的结果 入栈，栈中为： G+H(在这里方便讲解 标记为 G+H)
   4)扫描 F 为数字 ,入栈 ，栈中为 F, G+H
   5)扫描 / 为运算符, 依次弹出 F,G+H ，计算F/(G+H) 的结果入栈 ，栈中为 F/(G+H)
   6)扫描 E 为数字,入栈，栈中为 E, F/(G+H)
   7)扫描 / 为运算符, 依次弹出E, F/(G+H) ，计算 E/(F/(G+H))
   8)扫描 D 为数字,入栈 栈中为:D, E/(F/(G+H))
   9)扫描 C 为数字,入栈 栈中为:C,D, E/(F/(G+H))
   10)扫描 B 为数字,入栈 栈中为:B,C,D, E/(F/(G+H))
   11)扫描 A 为数字,入栈 栈中为:A,B,C,D, E/(F/(G+H))
   12)扫描^ 为运算符,依次弹出 A,B 计算 A^B的结果入栈, 栈中为：A^B ,C,D, E/(F/(G+H))
   13)扫描为运算符,依次弹出 A^B,C 计算 A^BC的结果入栈, 栈中为：A^B* C,D, E/(F/(G+H))
   14)扫描-为运算符,依次弹出 A^BC,D 计算 A^BC-D的结果入栈, 栈中为：A^B* C-D, E/(F/(G+H))
   15)扫描+为运算符,依次弹出 A^BC-D, E/(F/(G+H)) 计算 A^BC-D+ E/(F/(G+H)) 的到结果
   最后得到的表达式为： A^B* C-D+ E/(F/(G+H))

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

代码实现中缀2前缀

中缀表达式转前缀表达式，利用前缀表达式求结果。

import java.util.ArrayList; import java.util.Collections; import java.util.List; / * @Auther: 我爱双面奶 * @Date: 2018/7/18 22:53 * @Description: 中缀(infix)表达式转波兰式(polish notation)(前缀表达式) * */ public class InfixToPNCalculate { 
    public static void main(String[] args) { 
    String str = "1+(6/2)-8*2+(20-4)"; List<String> pnStack = infixToPn(str); int result = getResrult(pnStack); System.out.println("结果："+result); } / * 中缀转前缀表达式算法 * * 1、初始化两个栈：运算符栈opStack和存储前缀表达式栈pnStack； * 2、【反转】字符串，【从左至右】扫描中缀表达式； * 3、遇到操作数时，直接将其压入tempStack中； * 4、遇到运算符时，比较其与opStack栈顶运算符的优先级： * 4.1、如果opStack为空，或者栈顶运算符为右括号’)’，则直接将此运算符压入opStack中； * 4.2、否则，若优先级比栈顶运算符的优先级高或相等，则直接将此运算符压入opStack中； * 4.3、否则，将opStack栈顶的运算符弹出并压入到tempStack中，再次转入步骤4，与opStack中新的栈顶运算符相比较； * 5、遇到括号时： * 5.1、如果是右括号’)’，则直接压入opStack中； * 5.2、如果是左括号’(‘，则依次弹出opStack栈顶的运算符并压入tempStack中，知道遇到右括号’)’为止，此时将这一对括号丢弃； * 6、重复步骤2~5，直到表达式的最左边； * 7、将opStack中剩余的运算符依次弹出并压入tempStack中； * 8、依次弹出tempStack中的元素保存到result中，result即为中缀表达式转换所得的前缀表达式。 * @param strExpression 前缀表达式 * @return 后缀表达式 */ public static List<String> infixToPn(String strExpression){ 
    StringBuilder stringBuilder = new StringBuilder(strExpression.trim());//将String对象转换为StringBuilder对象，为了转字符串 System.out.println("中缀表达式："+stringBuilder); stringBuilder = stringBuilder.reverse();//反转字符串 List<String> pnStack = new ArrayList();//前缀表达式栈 List<String> opStack = new ArrayList();//运算符栈 String falg = ""; char[] str = stringBuilder.toString().toCharArray(); //从左往右扫描 for(int i=0;i<str.length;i++ ){ 
    if(isDigit((falg+str[i]).trim())){ 
   //判断flag+当前字符是否为数字 falg = (falg+str[i]).trim(); if(i==str.length-1){ 
   //当当前字符是数字，并且是最后一个字符时直接存入前缀表达式栈 //由于之前反转了，现在要反转回来，比如45在之前被反转为了54，需要反转回来 pnStack.add(new StringBuilder(falg).reverse().toString()); } }else { 
   //当当前字符不是数字时 if(falg.trim()!=""&&isDigit((falg).trim())){ 
   //将上一次的flag存入前缀表达式栈 pnStack.add(new StringBuilder(falg).reverse().toString()); falg=""; } if(opStack.size()==0||opStack.get(opStack.size()-1).equals(")")){ 
   //对应4.1 opStack.add(String.valueOf(str[i])); }else if(str[i]==')'){ 
   //对应5.1 opStack.add(String.valueOf(str[i])); }else if(str[i]=='('){ 
   //对应5.2 while (opStack.size()!=0){ 
    if(opStack.get(opStack.size()-1).equals(")")){ 
    opStack.remove(opStack.size()-1); break; } pnStack.add(opStack.get(opStack.size()-1)); opStack.remove(opStack.size()-1); } }else if (str[i]=='*'||str[i]=='/'){ 
   //对应4.2 opStack.add(String.valueOf(str[i])); }else if(opStack.get(opStack.size()-1).equals("*")||opStack.get(opStack.size()-1).equals("/")){ 
   //对应4.3 pnStack.add(opStack.get(opStack.size()-1)); opStack.remove(opStack.size()-1); i--; }else { 
   //对应4.2 opStack.add(String.valueOf(str[i])); } } } //对应7 while (opStack.size()!=0){ 
    pnStack.add(opStack.get(opStack.size()-1)); opStack.remove(opStack.size()-1); } //反转List对象 Collections.reverse(pnStack); System.out.print("波兰式(前缀表达式)："); pnStack.stream().forEach(x-> System.out.print(x+" "));//迭代输出 System.out.println(""); return pnStack; } / * 通过前缀表达式计算结果 * 1、借助中间结果栈tempStack，【从右至左】扫描表达式 * 2、遇到操作数时，将操作数入tempStack栈 * 3、遇到操作符时，从tempStack栈中弹出两个操作数，进行运行，然后将运算结果压入tempStack栈。 * 4、重复1~3，直到pnStack为空 * 5、tempStack栈剩下的最后一个元素即所求结果 * @param pnStack 中间结果栈 * @return */ public static int getResrult(List<String> pnStack){ 
    int result = 0; List<String> tempResultStack = new ArrayList<>(); while (pnStack.size()!=0){ 
    int end = pnStack.size()-1; int resultend = tempResultStack.size()-1; if(isDigit(pnStack.get(end))){ 
   //对应2 tempResultStack.add(pnStack.get(end)); pnStack.remove(end); }else { 
   //对应3 if(pnStack.get(end).equals("*")) { 
    result = Integer.parseInt(tempResultStack.get(resultend)) * Integer.parseInt(tempResultStack.get((resultend - 1))); }else if (pnStack.get(end).equals("/")){ 
    result = Integer.parseInt(tempResultStack.get(resultend)) / Integer.parseInt(tempResultStack.get((resultend - 1))); }else if (pnStack.get(end).equals("+")){ 
    result = Integer.parseInt(tempResultStack.get(resultend)) + Integer.parseInt(tempResultStack.get((resultend - 1))); }else if (pnStack.get(end).equals("-")){ 
    result = Integer.parseInt(tempResultStack.get(resultend)) - Integer.parseInt(tempResultStack.get((resultend - 1))); } pnStack.remove(end); tempResultStack.remove(resultend); tempResultStack.remove(resultend-1); tempResultStack.add(String.valueOf(result)); } } // System.out.println(tempResultStack.toString()); return result; } / * 判断一个字符串是否为数值 * @param str 判断的字符串 * @return 返回一个boolean值 */ public static boolean isDigit(String str){ 
    return str.matches("[0-9]{1,}"); } } 

附录