java实现中缀表达式转后缀表达式

简介

算数公式有3种表示方法，前缀表达式，中缀表达式，后缀表达式，区别在于运算符相对于操作数的位置不同。中缀表达式对于人来说很好理解，但对计算机来说很复杂，所以一般会将中缀转前缀或后缀来处理。

• 举例如下

(3 + 4) × 5 - 6 中缀表达式
- × + 3 4 5 6 前缀表达式
3 4 + 5 × 6 - 后缀表达式

代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.function.BiFunction;

class Solution {

  private static final Map<Character, Integer> operatorPriorityMap =
      Map.of('+', 1, '-', 1, '*', 2, '/', 2);

  private static final Map<Character, BiFunction<Integer, Integer, Integer>> operandsMap = Map.of(
      '+', (x, y) -> x + y,
      '-', (x, y) -> x - y,
      '*', (x, y) -> x * y,
      '/', (x, y) -> x / y);

  public int calculate(String infix) {
    return calcSuffix(infix2suffix(infix));
  }

  /**
   * 后缀表达式计算
   */
  private int calcSuffix(List<Node> suffix) {
    Stack<Integer> stack = new Stack<>();
    Set<Character> operatorSet = operatorPriorityMap.keySet();
    for (Node node : suffix) {
      if (node.operational) {
        stack.push(node.operands);
      } else if (operatorSet.contains(node.operator)) {
        int num2 = stack.pop();
        int num1 = stack.pop();
        stack.push(operandsMap.get(node.operator).apply(num1, num2));
      } else {
        throw new RuntimeException("illegal expression");
      }
    }
    return stack.pop();
  }

  /**
   * 中缀表达式转后缀表达式
   */
  private List<Node> infix2suffix(String infix) {
    List<Node> res = new ArrayList<>();
    Stack<Character> stack = new Stack<>();
    Set<Character> operatorSet = operatorPriorityMap.keySet();
    for (int i = 0; i < infix.length(); i++) {
      char item = infix.charAt(i);
      //是数字，直接添加到结果列表
      if (Character.isDigit(item)) {
        int num = 0;
        while (i < infix.length()) {
          item = infix.charAt(i);
          if (!Character.isDigit(item)) {
            i--;
            break;
          }
          num = num * 10 + (item - '0');
          i++;
        }
        res.add(new Node(num));
        continue;
      }
      if (item == ' ') {
        continue;
      }
      //是左括号，入栈
      if (item == '(') {
        stack.push(item);
      } else if (item == ')') {
        //是右括号，依次出栈，直到左括号
        while (true) {
          char pop = stack.pop();
          if (pop == '(') {
            break;
          }
          res.add(new Node(pop));
        }
      } else if (operatorSet.contains(item)) {
        //-操作符特殊处理，有可能表示负数
        if (item == '-') {
          //-字符前一个字符如果为空或为左括号或为操作符，就表示负数
          if (i == 0 || infix.charAt(i - 1) == '(' || operatorSet.contains(infix.charAt(i - 1))) {
            res.add(new Node(0));
            stack.push(item);
            continue;
          }
        }
        //是操作符，依次出栈，直到栈为空或栈顶为左括号或当前操作符比栈顶操作符优先级高，当前操作符入栈
        while (true) {
          if (stack.isEmpty()
              || stack.peek() == '('
              || operatorPriorityMap.get(item) > operatorPriorityMap.get(stack.peek())) {
            break;
          }
          res.add(new Node(stack.pop()));
        }
        stack.push(item);
      } else {
        throw new RuntimeException("illegal expression");
      }
    }
    while (!stack.isEmpty()) {
      res.add(new Node(stack.pop()));
    }
    return res;
  }

  static class Node {

    //操作数
    int operands;
    //操作符
    char operator;
    //是否为操作数
    boolean operational;

    Node(int operands) {
      this.operands = operands;
      this.operational = true;
    }

    Node(char operator) {
      this.operator = operator;
      this.operational = false;
    }

  }

  public static void main(String[] args) {
    //支持负数
    System.out.println(new Solution().calculate("(-12+(4+-5*2)-(-3))+(6+8)"));
    System.out.println(new Solution().calculate("(6)-(8)-(17)+(1+(6))"));
  }
}

支持加减乘除、括号的处理，支持负数。