4.中缀表达式转后缀表达式的应用:实现多位浮点数的加减乘除运算

先简单介绍几个概念:

1.前缀表达式
 
2.中缀表达式
 
3.后缀表达式
 

 

4.中缀表达式转后缀表达式的流程:

 

代码实现:

用于计算中作为存储结构的栈:

package com.vi.algorithm.stack;

import com.vi.algorithm.linear.LinkList;

//  计算器栈，用于实现加减乘除的计算器,在链表实现的栈的基础上，对功能做扩展
public class CalculateStack<T> extends LinkListStack<T> {

    public CalculateStack() {
    }

    //  判断当前元素是否操作符
    public static boolean isCommand(String str) {
        return str.matches("[\+\-\*\/]");
    }

    //  判断当前操作符的优先级
    public static int priority(String str) {
        if ("+".equals(str))
            return 0;
        if ("-".equals(str))
            return 1;
        if ("*".equals(str) || "/".equals(str))
            return 2;
        if("(".equals(str) || ")".equals(str))
            return -1;
        throw new RuntimeException("非法操作符");
    }

    public static void main(String[] args) {
//        System.out.println(new CalculateStack<>().isCommand("\"));
        CalculateStack<Integer> cs = new CalculateStack<>();
        cs.push(1);
        cs.push(2);
        cs.push(3);

        System.out.println(cs.peek());
        cs.list();
    }

}

实现栈用到的两个类:

 1 package com.vi.algorithm.stack;
 2 
 3 import com.vi.algorithm.linear.LinkList;
 4 
 5 //  用链表实现栈
 6 public class LinkListStack<T> {
 7     private LinkList<T> stack;
 8 
 9     public LinkListStack() {
10         stack = new LinkList<>();
11     }
12 
13     //  链表式的不存在存满的情况
14     public boolean isFull() {
15         return false;
16     }
17 
18     //  判断是否为空
19     public boolean isEmpty() {
20         return stack.length() == 0;
21     }
22 
23     public T pop() {
24         if (stack.isEmpty()) {
25             System.out.println("栈为空！");
26             return null;
27         }
28         T result = stack.remove(stack.length() - 1);
29         return result;
30     }
31 
32     public boolean push(T data) {
33         try {
34             stack.insert(data);
35         } catch (Exception e) {
36             System.out.println("插入失败！");
37             return false;
38         }
39         return true;
40     }
41 
42     //  查看栈顶元素但是不弹出
43     public T peek() {
44         return stack.get(stack.length() - 1);
45     }
46 
47     //  遍历
48     public void list() {
49         if (stack.isEmpty()) {
50             System.out.println("栈为空！");
51             return;
52         }
53         for (int i = stack.length() - 1; i >= 0; i--) {
54             System.out.printf("stack[%d] = %d
", i, stack.get(i));
55         }
56     }
57 }
计算栈的父类栈

链表:

  1 package com.vi.algorithm.linear;
  2 
  3 import java.util.Iterator;
  4 
  5 /**
  6  * 单向链表
  7  */
  8 public class LinkList<T> implements Iterable<T> {
  9     // 头结点
 10     private Node<T> head;
 11     // 链表长度
 12     private int length;
 13 
 14     public LinkList() {
 15         head = new Node<>(null, null);
 16         length = 0;
 17     }
 18 
 19     // 内部类，节点类型
 20     private class Node<T> {
 21         T data;
 22         Node next;
 23 
 24         public Node(T data, Node next) {
 25             this.data = data;
 26             this.next = next;
 27         }
 28 
 29         @Override
 30         public String toString() {
 31             return "Node{" +
 32                     "data=" + data +
 33                     ", next=" + next +
 34                     '}';
 35         }
 36     }
 37 
 38     // 清空链表
 39     public void clear() {
 40         if (head == null)
 41             return;
 42         head.next = null;
 43         length = 0;
 44     }
 45 
 46     // 判断链表是否为空
 47     public boolean isEmpty() {
 48         return length == 0;
 49     }
 50 
 51     // 获取链表中元素的个数
 52     public int length() {
 53         return length;
 54     }
 55 
 56     // 获取第i个元素的值
 57     public T get(int i) {
 58         if (head == null)
 59             return null;
 60         Node cursor = head;
 61         for (int index = 0; index <= i; index++) {
 62             if (cursor.next != null)
 63                 cursor = cursor.next;
 64             else
 65                 throw new RuntimeException("下标越界");
 66         }
 67         return (T) cursor.data;
 68     }
 69 
 70     // 在链表索引i处插入元素t
 71     public void insert(int i, T t) {
 72         if (head == null)
 73             return;
 74         Node cursor = head;
 75 
 76         int index = 0;
 77         while (index <= i - 1) {
 78             if (cursor != null) {
 79                 cursor = cursor.next;
 80             } else
 81                 throw new RuntimeException("下标越界");
 82             index++;
 83         }
 84 
 85         if (cursor != null) {
 86             if (cursor.next != null) {
 87                 Node newNode = new Node(t, cursor.next);
 88                 cursor.next = newNode;
 89             } else {
 90                 Node newNode = new Node(t, null);
 91                 cursor.next = newNode;
 92             }
 93             length++;
 94         }
 95     }
 96 
 97     // 在链表最后的位置插入一个元素
 98     public void insert(T t) {
 99         if (head == null)
100             return;
101 
102         insert(length, t);
103     }
104 
105     // 删除链表中索引i处的元素并返回
106     public T remove(int i) {
107         if (head == null)
108             return null;
109         Node cursor = head;
110         for (int index = 0; index <= i - 1; index++) {
111             if (cursor.next == null)
112                 throw new RuntimeException("下标越界");
113             cursor = cursor.next;
114         }
115 
116         if (cursor.next == null) {
117             return null;
118         } else {
119             Node target = cursor.next;
120             Node next = target.next;
121             cursor.next = next;
122             target.next = null;
123             length--;
124             return (T) target.data;
125         }
126     }
127 
128     // 查找t在链表中的索引位置，如果不存在返回-1
129     public int indexOf(T t) {
130         Node cursor = head.next;
131         int index = 0;
132         while (cursor != null) {
133             if (cursor.data.equals(t)) {
134                 return index;
135             }
136             index++;
137             cursor = cursor.next;
138         }
139         return -1;
140     }
141 
142     @Override
143     public Iterator<T> iterator() {
144         return new Literator();
145     }
146 
147     private class Literator implements Iterator {
148         Node cursor;
149 
150         public Literator() {
151             cursor = head;
152         }
153 
154         @Override
155         public boolean hasNext() {
156             return cursor.next != null;
157         }
158 
159         @Override
160         public Object next() {
161             cursor = cursor.next;
162             return cursor;
163         }
164     }
165 }
View Code

将中缀表达式转成后缀表达式以及计算表达式的值

  1 package com.vi.algorithm.demo;
  2 
  3 import com.vi.algorithm.stack.CalculateStack;
  4 
  5 import java.math.BigDecimal;
  6 import java.util.ArrayList;
  7 import java.util.Arrays;
  8 import java.util.List;
  9 import java.util.Stack;
 10 
 11 //  波兰表达式计算(后缀表达式) 
 12 public class PolandCalculations {
 13     public static void main(String[] args) { // 1+(2*3)+4
 14         String expression  = infixToSuffix("3.1+4.2*5.6-4.6");
 15         System.out.println(expression);
 16         System.out.println("计算的结果是:"+calculate(expression));
 17     }
 18 
 19     //  多位正浮点数计算
 20     public static float calculate(String expression) {
 21         // (30+4)*5-6 -> 30 4 + 5 * 6 -
 22         String[] target = expression.split(" ");
 23         List<String> strings = Arrays.asList(target);
 24         Stack<String> numberStack = new Stack<>();
 25         for (String str : strings) {
 26             if (str.matches("[\+\-\*\/]")) {
 27                 //  如果是运算符，从数栈中弹出两个数进行计算
 28                 BigDecimal num2 = new BigDecimal(numberStack.pop());
 29                 BigDecimal num1 = new BigDecimal(numberStack.pop());
 30                 float result = calculate(num1, num2, str);
 31                 //  把计算出的结果压入数栈
 32                 numberStack.push(result + "");
 33             } else {
 34                 //  如果是运算符，压入数栈
 35                 numberStack.push(str);
 36             }
 37         }
 38         return Float.parseFloat(numberStack.pop());
 39     }
 40 
 41     private static float calculate(BigDecimal num1, BigDecimal num2, String str) {
 42         if ("+".equals(str))
 43             return num1.add(num2).floatValue();
 44         if ("-".equals(str))
 45             return num1.subtract(num2).floatValue();
 46         if ("*".equals(str))
 47             return num1.multiply(num2).floatValue();
 48         if ("/".equals(str))
 49             return num1.divide(num2).floatValue();
 50         throw new RuntimeException("非法的操作符");
 51     }
 52 
 53     /**
 54      * 中缀表达式转后缀表达式，假设输入的中缀表达式都是符合规范的
 55      * 思路:
 56      * 1.准备两个栈，一个s1存操作符，另一个s2存处理以后的表达式
 57      * 2.遍历中序表达式，遇到数，压入s2栈,遇到操作符进行判断，如果s1为空，直接压入s1,如果不为空，判断是否"(","("直接压入
 58      * 3.判断是否")"，如果是，弹出s1中的元素，依次压入s1栈，直至遇到"(",将"("弹出
 59      * 4.如果不是以上情况，则判断当前运算符的优先级是否高于栈顶运算符的优先级，如果高于栈顶，把当前运算符压入s1，如果低于栈顶，把栈顶弹出压入s2,依次和新栈顶继续比较
 60      * 5.遍历结束，把s1元素弹出依次压入s2,倒序输出s2元素，即转换后的后缀表达式
 61      *
 62      * @param infixExpression
 63      * @return
 64      */
 65     private static String infixToSuffix(String infixExpression) {
 66         //  把字符串表达式转换成列表
 67         int index = 0;
 68         ArrayList<String> list = new ArrayList<>();
 69         //  把运算符存进列表
 70         while (index < infixExpression.length()) {
 71             if (infixExpression.substring(index, index + 1).matches("[()\+\-\*\/]")) {
 72                 list.add(infixExpression.substring(index, index + 1));
 73             } else {
 74                 //  把操作数存进列表
 75                 String num = infixExpression.substring(index, index + 1);
 76                 while (index != infixExpression.length() - 1 && !infixExpression.substring(index + 1, index + 2).matches("[()\+\-\*\/]")) {
 77                     index++;
 78                     num = num + infixExpression.substring(index, index + 1);
 79                 }
 80                 list.add(num);
 81             }
 82             index++;
 83         }
 84         //  准备一个栈存放运算符
 85         CalculateStack<String> stack = new CalculateStack<>();
 86         //  准备一个列表存放结果
 87         ArrayList<String> result = new ArrayList<>();
 88         //  顺序遍历集合
 89         for (int i = 0; i < list.size(); i++) {
 90             if (!list.get(i).matches("[()\+\-\*\/]")) {
 91                 //  如果不是运算符，直接存入result
 92                 result.add(list.get(i));
 93             } else {
 94                 //  如果是运算符
 95                 if (stack.isEmpty()) {
 96                     //  栈为空，直接压入
 97                     stack.push(list.get(i));
 98                 } else if ("(".equals(list.get(i))) {
 99                     //  如果是左括号，直接压入
100                     stack.push(list.get(i));
101                 } else if (")".equals(list.get(i))) {
102                     //  如果是右括号，弹出栈顶元素直到"("
103                     while (!"(".equals(stack.peek())) {
104                         result.add(stack.pop());
105                     }
106                     stack.pop();
107                 } else {
108                     //  判断运算符优先级
109                     if (CalculateStack.priority(list.get(i)) > CalculateStack.priority(stack.peek())) {
110                         stack.push(list.get(i));
111                     } else {
112                         while (!stack.isEmpty() && CalculateStack.priority(stack.peek()) >= CalculateStack.priority(list.get(i))) {
113                             result.add(stack.pop());
114                         }
115                         stack.push(list.get(i));
116                     }
117                 }
118             }
119         }
120         while (!stack.isEmpty()) {
121             result.add(stack.pop());
122         }
123         //  把列表转成字符串
124         final String[] str = {""};
125         result.forEach(ele -> {
126             str[0] = str[0] + ele +" ";
127         });
128         return str[0].substring(0,str[0].length()-1);
129     }
130 }
View Code

运行结果如下:

当前代码并不支持负数的计算，如果要加入对负数的运算，可以先把中缀表达式处理一下，例如:判断开头是否有负数,如果有将 -99之类的负数转成(0-99),再将表达式其他的(-xx)这样的项数替换成(0-99),

再转换成后缀表达式计算即可。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/blogforvi/p/13769708.html