Java实现由中缀表达式转为前缀表达式

      PS:

     这段时间一直在找实习，在这条路上的风景对我来说并不是那么写意，期间发现自己的知识还是不成体系，平时用的很多的东西在表达时就完全不是那么回事了。姑且把这看成一个学习的过程吧，接下来我会陆续的把这些题重做一次，希望会得到成长！那么就从最近的“前缀表达式”开始吧！ 接下来的内容将围绕这两个问题展开：

1.为什么要把中缀表达式转化成前缀表达式？

2.怎么把中缀表达式转化成前缀表达式并计算（描述并JAVA实现）？

一. 先来回答为什么要把中缀表达式转化成前缀表达式？

中缀表达式（或中缀记法）是一个通用的算术或逻辑公式表示方法,与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。

二. 怎么把中缀表达式转化成前缀表达式并计算?

 

      前缀表达式

     前缀表达式就是前序表达式。

      前缀表达式就是不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，为纪念其发明者波兰数学家Jan Lukasiewicz也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。

     由中缀表达式转为前缀表达式的步骤

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从右至左扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：

• 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
• 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
• 否则，将S1栈顶的运算符弹出并压入到S2中，再与S1中新的栈顶运算符相比较；

5. 遇到括号时：

•   如果是右括号“)”，则直接压入S1；
•  如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号 丢弃；

6. 重复步骤2至5，直到表达式的最左边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

    例如，将中缀表达式“(3+4)-5*9”转换为前缀表达式的过程如下：

扫描到的元素	S2(栈底->栈顶)	S1 (栈底->栈顶)	说明
6	6	空	数字直接入栈
*	6	*	S1为空，运算符直接入栈
5	65	*	数字直接入栈
-	65*	-	优先级小于栈顶元素
)	65*	-）	右括号直接入栈
4	654*	-）	数字直接入栈
+	654*	-）+	S1栈顶是右括号，直接入栈
3	6543*	-）+	数字直接入栈
(	6543*+-	空	左括号，弹出运算符直至遇到右括号
到达最左端	6543*+-	空	S1中剩余的运算符

    

      JAVA代码实现：

import java.util.Stack;
/**
 * 以整型数为例测试中缀表达式转换成前缀表达式的计算问题
 * @author where
 *
 */
public class TestForExpression {

      public static void main(String[] args) {
          String input_expression = "(3+4)-5*9" ;
          System. out .println("待测试的中缀表达式为：" +input_expression);
          System. out .print("相应的前缀表达式为：" );
           toPrefixExpression(input_expression);

     }
      /**
      * 将中缀表达式转化为前缀表达式
      * @param input 要被转化的中缀表达式
      */
      public static void  toPrefixExpression(String input){
           int len = input.length();//中缀表达式的长度
           //System.out.println("读到的字符串为："+input+"长度为："+ len);
           char c,tempChar;//这两个都是中间变量，c用来存放循环中的对应位置的字符，
          Stack<Character> s1 = new Stack<Character>();//实例化一个符号栈
          Stack<Integer> s2 = new Stack<Integer>();//实例化一个数字栈
          Stack< Object> expression = new Stack< Object>();  //实例化一个前缀表达式的栈
           //从右至左扫描表达式
           for (int i=len-1; i>=0; --i) { 
             c = input.charAt(i);
             //判断读取的是不是数字，是的话将数字压入操作数栈和表达式栈
             if (Character.isDigit(c)) {
               String s = String. valueOf(c);
               //再转换成 Int类型：
               int j = Integer.parseInt(s);
                   s2.push(j); 
                   expression.push(j); 
             } else if (isOperator(c)) {
               //如果当前字符为运算符（包含括号）
                   while (!s1.isEmpty() 
                               && s1.peek() != ')' 
                               && priorityCompare(c, s1.peek()) < 0) { 
                      //当前运算符栈不为空且要运算符栈顶运算符不是右括号且当前运算符的优先级比运算符栈顶运算符的优先级低，
                      //则将运算符栈栈顶元素拿出来与操作数栈的两个栈顶元素进行运算并把运算结果压入操作数栈
                         expression.push(s1.peek()); 
                         s2.push( calc(s2.pop(), s2.pop(), s1.pop())); 
                   } 
                   s1.push(c); 
             } else if (c == ')' ) {
               //因为我们是从右至左来扫描中缀表达式的所以对于一个“（）”而言一定是先读到右边的括号
                   s1.push(c); 
             } else if (c == '(' ) { 
               //如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入表达式栈，直到遇到左括号为止，此时将这一对括号丢弃；
                   while ((tempChar=s1.pop()) != ')' ) { 
                         expression.push(tempChar); 
                         s2.push( calc(s2.pop(), s2.pop(), tempChar)); 
                         if (s1.isEmpty()) { 
                               throw new IllegalArgumentException( 
                                     "bracket dosen't match, missing right bracket ')'."); 
                         } 
                   } 
             } else if (c == ' ' ) { 
                   // 如果表达式里包含空格则不处理空格
             } else { 
                   throw new IllegalArgumentException( 
                               "wrong character '" + c + "'" ); 
             } 
           }
           while (!s1.isEmpty()) { 
             tempChar = s1.pop(); 
             expression.push(tempChar); 
             s2.push( calc(s2.pop(), s2.pop(), tempChar)); 
           } 
           while (!expression.isEmpty()) { 
             System. out .print(expression.pop() + " " ); 
           } 
           int result = s2.pop(); 
           if (!s2.isEmpty()) 
             throw new IllegalArgumentException( "input is a wrong expression.");  
           System. out .println(); 
         System. out .println("计算结果为： " + result); 
          
     }
      /**
      * 对给定的两个操作数及操作符进行计算
      * @param num1
      * @param num2
      * @param op
      * @return 返回计算整型结果
      */
      private static Integer calc( int num1, int num2, char op) {
       
            switch (op) { 
            case '+' : 
                  return num1 + num2; 
            case '-' : 
                  return num1 - num2; 
            case '*' : 
                  return num1 * num2; 
            case '/' : 
                  if (num2 == 0) throw new IllegalArgumentException("divisor can't be 0." ); 
                  return num1 / num2; 
            default : 
                  return 0; // will never catch up here 
            } 
       
     }
      /**
      * 判断字符是否是操作符的方法
      * @param c
      * @return
      */
      private static boolean isOperator( char c) {
                return (c=='+' || c=='-' || c=='*' || c=='/' ); 
     }
      /**
      * 判断运算符优先级的方法
      * @param op1
      * @param op2
      * @return 返回值如果是:
      *          - 1则表示op1的优先级低于op2,
      *           0 则表示op1的优先级等于op2，
      *           1则表示op1的优先级高于op2。
      */
      private static int priorityCompare( char op1, char op2) { 
         switch (op1) { 
         case '+' : case '-': 
               return (op2 == '*' || op2 == '/' ? -1 : 0); 
         case '*' : case '/': 
               return (op2 == '+' || op2 == '-' ? 1 : 0); 
         } 
         return 1; 
   } 
 

}

   测试结果：

待测试的中缀表达式为：(3+4)-5*9
相应的前缀表达式为：- + 3 4 * 5 9 
计算结果为： -38

 （说明：为了方便说明整个转化方法，我已整型运算为例，如果要考虑的更全面的话可以用               Double型，只不过在对“.”的时候要注意）

时间不早了，明天还有课，博客就先写到这，明天继续下一题搞起！！！