前缀、中缀、后缀表达式(逆波兰表达式)

男娘i 2022-03-29 12:20 298阅读 0赞

转载自：[https://www.cnblogs.com/chensongxian/p/7059802.html][https_www.cnblogs.com_chensongxian_p_7059802.html]

# 前缀、中缀、后缀表达式(逆波兰表达式) #

## 介绍 ##

> 前缀表达式、中缀表达式、后缀表达式都是四则运算的表达方式,用以四则运算表达式求值  
> ,即数学表达式的求职

## 中缀表达式 ##

### 简介 ###

> 中缀表达式就是常见的运算表达式，如(3+4)×5-6

## 前缀表达式 ##

### 简介 ###

> 前缀表达式又称波兰式，**前缀表达式的运算符位于操作数之前**

> 比如:**- × + 3 4 5 6**

### 前缀表达式的计算机求值 ###

> 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

*  例如:**- × + 3 4 5 6**
    
    > 1.  从右至左扫描，将6、5、4、3压入堆栈
    > 2.  遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈
    > 3.  接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
    > 4.  最后是-运算符，计算出35-6的值，即29，由此得出最终结果

### 将中缀表达式转换为前缀表达式 ###

> **转换步骤如下**:

1.  初始化两个栈:运算符栈s1，储存中间结果的栈s2
2.  从右至左扫描中缀表达式
3.  遇到操作数时，将其压入s2
4.  遇到运算符时，比较其与s1栈顶运算符的优先级
    
    1.  如果s1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
    2.  否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1
    3.  否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
5.  遇到括号时
    
    1.  如果是右括号“)”，则直接压入s1
    2.  如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
6.  重复步骤2至5，直到表达式的最左边
7.  将s1中剩余的运算符依次弹出并压入s2
8.  依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式

> **例如:1+((2+3)×4)-5具体过程，如下表**

<table> 
 <thead> 
  <tr> 
   <th>扫描到的元素</th> 
   <th>S2(栈底-&gt;栈顶)</th> 
   <th>S1 (栈底-&gt;栈顶)</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>5</td> 
   <td>空</td> 
   <td>数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td>-</td> 
   <td>5</td> 
   <td>-</td> 
   <td>s1为空，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td>)</td> 
   <td>5</td> 
   <td>-)</td> 
   <td>右括号直接入栈</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>5 4</td> 
   <td>-)</td> 
   <td>数字直接入栈</td> 
  </tr> 
  <tr> 
   <td>x</td> 
   <td>5 4</td> 
   <td>-)x</td> 
   <td>s1栈顶是右括号，直接入栈</td> 
  </tr> 
  <tr> 
   <td>)</td> 
   <td>5 4</td> 
   <td>-)x)</td> 
   <td>右括号直接入栈</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>5 4 3</td> 
   <td>-)x)</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>5 4 3</td> 
   <td>-)x)+</td> 
   <td>s1栈顶是右括号，直接入栈</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>5 4 3 2</td> 
   <td>-)x)+</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>(</td> 
   <td>5 4 3 2 +</td> 
   <td>-)x</td> 
   <td>左括号，弹出运算符直至遇到右括号</td> 
  </tr> 
  <tr> 
   <td>(</td> 
   <td>5 4 3 2 + x</td> 
   <td>-</td> 
   <td>同上</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>5 4 3 2 + x</td> 
   <td>-+</td> 
   <td>优先级与-相同，入栈</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>5 4 3 2 + x 1</td> 
   <td>-+</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>到达最左端</td> 
   <td>5 4 3 2 + x 1 + -</td> 
   <td>空</td> 
   <td>s1剩余运算符</td> 
  </tr> 
 </tbody> 
</table>

> **结果是:- + 1 × + 2 3 4 5**

## 后缀表达式 ##

### 简介 ###

> 后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后

> 比如:**3 4 + 5 × 6 -**

### 后缀表达式计算机求值 ###

> 与前缀表达式类似，只是顺序是从左至右：

> 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

> **例如后缀表达式“3 4 + 5 × 6 -”**：

1.  从左至右扫描，将3和4压入堆栈；
2.  遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
3.  将5入栈；
4.  接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5.  将6入栈；
6.  最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

### 将中缀表达式转换为后缀表达式 ###

> 与转换为前缀表达式相似，步骤如下：

1.  初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2.  从左至右扫描中缀表达式；
3.  遇到操作数时，将其压s2；
4.  遇到运算符时，比较其与s1栈顶运算符的优先级：
    
    1.  如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
    2.  否则，若优先级比栈顶运算符的高，也将运算符压入s1（**注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况**）；
    3.  否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5.  遇到括号时：
    
    1.  如果是左括号“(”，则直接压入s1；
    2.  如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
6.  重复步骤2至5，直到表达式的最右边；
7.  将s1中剩余的运算符依次弹出并压入s2；
8.  依次弹出s2中的元素并输出，**结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）**

> **例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下**：

<table> 
 <thead> 
  <tr> 
   <th>扫描到的元素</th> 
   <th>s2(栈底-&gt;栈顶)</th> 
   <th>s1 (栈底-&gt;栈顶)</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>空</td> 
   <td>数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>1</td> 
   <td>+</td> 
   <td>s1为空，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td>(</td> 
   <td>1</td> 
   <td>+ (</td> 
   <td>左括号，直接入栈</td> 
  </tr> 
  <tr> 
   <td>(</td> 
   <td>1</td> 
   <td>+ ( (</td> 
   <td>同上</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1 2</td> 
   <td>+ ( (</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>1 2</td> 
   <td>+ ( ( +</td> 
   <td>s1栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>1 2 3</td> 
   <td>+ ( ( +</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>)</td> 
   <td>1 2 3 +</td> 
   <td>+ (</td> 
   <td>右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr> 
   <td>×</td> 
   <td>1 2 3 +</td> 
   <td>+ ( ×</td> 
   <td>s1栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>1 2 3 + 4</td> 
   <td>+ ( ×</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>)</td> 
   <td>1 2 3 + 4 ×</td> 
   <td>+</td> 
   <td>右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr> 
   <td>-</td> 
   <td>1 2 3 + 4 × +</td> 
   <td>-</td> 
   <td>-与+优先级相同，因此弹出+，再压入-</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>1 2 3 + 4 × + 5</td> 
   <td>-</td> 
   <td>数字</td> 
  </tr> 
  <tr> 
   <td>到达最右端</td> 
   <td>1 2 3 + 4 × + 5 -</td> 
   <td>空</td> 
   <td>s1中剩余的运算符</td> 
  </tr> 
 </tbody> 
</table>

> **因此结果为“1 2 3 + 4 × + 5 -”**

## 代码实现 ##

public class Operation {
        private static int ADDITION=1;
        private static int SUBTRACTION=1;
        private static int MULTIPLICATION=2;
        private static int DIVISION=2;
    
        public static int getValue(String operation){
            int result;
            switch (operation){
                case "+":
                    result=ADDITION;
                    break;
                case "-":
                    result=SUBTRACTION;
                    break;
                case "*":
                    result=MULTIPLICATION;
                    break;
                case "/":
                    result=DIVISION;
                    break;
                default:
    //                System.out.println("不存在该运算符");
                    result=0;
            }
            return result;
        }
    }
    
    
    
    public class PolishNotation {
    
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            System.out.println("请输入运算表达式:");
            String expressionStr=sc.nextLine();
    //        System.out.println(expressionStr);
            List<String> zx= toInfixExpression(expressionStr);
            List<String> rpn=parseSuffixExpression(zx);
            String rpnStr="";
            for(String str:rpn){
                rpnStr+=str;
            }
            System.out.println(rpnStr);
    
            System.out.println("计算结果:"+ calculate(rpn));
        }
    
        /**
         * 把字符串转换成中序表达式
         * @param s
         * @return
         */
        public static List<String> toInfixExpression(String s) {
            List<String> ls = new ArrayList<String>();//存储中序表达式
            int i = 0;
            String str;
            char c;
            do {
                if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                    ls.add("" + c);
                    i++;
                } else {
                    str = "";
                    while (i < s.length() && (c = s.charAt(i)) >= 48
                            && (c = s.charAt(i)) <= 57) {
                        str += c;
                        i++;
                    }
                    ls.add(str);
                }
    
            } while (i < s.length());
            return ls;
        }
    
        /**
         * 转换成逆波兰表达式
         * @param ls
         * @return
         */
        public static List<String> parseSuffixExpression(List<String> ls) {
            Stack<String> s1=new Stack<String>();
            Stack<String> s2=new Stack<String>();
            List<String> lss = new ArrayList<String>();
            for (String ss : ls) {
                if (ss.matches("\\d+")) {
                    lss.add(ss);
                } else if (ss.equals("(")) {
                    s1.push(ss);
                } else if (ss.equals(")")) {
    
                    while (!s1.peek().equals("(")) {
                        lss.add(s1.pop());
                    }
                    s1.pop();
                } else {
                    while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(ss)) {
                        lss.add(s1.pop());
                    }
                    s1.push(ss);
                }
            }
            while (s1.size() != 0) {
                lss.add(s1.pop());
            }
            return lss;
        }
    
        /**
         * 通过逆波兰表达式计算结果
         * @param ls
         * @return
         */
        public static int calculate(List<String> ls) {
            Stack<String> s=new Stack<String>();
            for (String str : ls) {
                if (str.matches("\\d+")) {
                    s.push(str);
                } else {
                    int b = Integer.parseInt(s.pop());
                    int a = Integer.parseInt(s.pop());
                    int result=0;
                    if (str.equals("+")) {
                        result = a + b;
                    } else if (str.equals("-")) {
                        result = a - b;
                    } else if (str.equals("*")) {
                        result = a * b;
                    } else if (str.equals("\\")) {
                        result = a / b;
                    }
                    s.push("" + result);
                }
            }
            System.out.println(s.peek());
            return Integer.parseInt(s.pop());
        }
    }

分类: [算][Link 1]

[https_www.cnblogs.com_chensongxian_p_7059802.html]: https://www.cnblogs.com/chensongxian/p/7059802.html
[Link 1]: https://www.cnblogs.com/chensongxian/category/1021073.html