数据结构与算法@中缀式转后缀式

发表于 | 分类于 | 评论数： | 阅读次数：

概述

算术表达式中缀式转后缀式，例如”A+(B-C/D)E” => “ABCD/-E+” ; “A+B-C/D” => “AB+CD/-“。
算法思路：https://blog.csdn.net/allinone99/article/details/81297098

详述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
function infix2suffix(infixExp) {
  // 判断操作符方法
  let isOperator = function(val) {
    return ["+", "-", "*", "/", "^", "(", ")"].indexOf(val) !== -1;
  };
  // 计算优先级方法
  let getPriority = function(val) {
    let result = 0;
    switch (val) {
      case "^":
        result = 3;
        break;
      case "*":
      case "/":
        result = 2;
        break;
      case "+":
      case "-":
        result = 1;
        break;
      default:
        break;
    }
    return result;
  };

  // 操作符存放栈
  let operatorStack = new Stack();
  let suffixExp = "";
  for (let i = 0; i < infixExp.length; i++) {
    const char = infixExp[i];

    if (isOperator(char)) {
      if (
        char === "(" ||
        operatorStack.length === 0 ||
        getPriority(char) > getPriority(operatorStack.peek())
      ) {
        operatorStack.push(char);
      } else if (char === ")") {
        while (!operatorStack.isEmpty()) {
          if (operatorStack.peek() === "(") {
            operatorStack.pop();
            break;
          } else {
            suffixExp += operatorStack.pop();
          }
        }
      } else {
        suffixExp += operatorStack.pop();
        operatorStack.push(char);
      }
    } else {
      suffixExp += char;
    }
  }
  // 读取完成，则将栈中剩余的运算符依次弹出到后缀表达式
  while (!operatorStack.isEmpty()) {
    suffixExp += operatorStack.pop();
  }
  return suffixExp;
}

let exp1 = "A+(B-C/D)*E";
let exp2 = "a+b*c+(d*e+f)*g";
let exp3 = "A+B-C/D";
console.log(exp1 + " => " + infix2suffix(exp1));
console.log(exp2 + " => " + infix2suffix(exp2));
console.log(exp3 + " => " + infix2suffix(exp3));

参考