聊聊前序、中序、后序表达式

在游戏开发中，我们经常需要在配置表中定义各种公式，比如 a * (b + c)，用来计算技能伤害、属性加成等。如果直接让程序在运行时解析并执行这些公式，就需要处理运算符优先级和括号等复杂问题。
这时，后序表达式就派上了用场。我们将中序表达式 a * (b + c) 转换为后序表达式 a b c + *，这样程序只需要一个栈就能高效计算，无需担心优先级和括号。
而要深入理解后序表达式，就不得不提到与之相关的完整概念体系：前序表达式、中序表达式和后序表达式。这三种表达式各有特点，共同构成了计算机处理数学表达式的理论基础。
 
1.中序(中缀)&前序表达式

中序表达式就是日常书写的公式，但这种日常公式对计算机并不友好，有括号、优先级等需要考虑，计算机直接读取较为麻烦
因此波兰数学家扬·武卡谢维奇发明了"波兰表示法"（前序表达式）
所以前序表达式又叫做 波兰式
 
例如LISP的语法风格就是基于前序表达式的：

1. ;; 中序: 1 + 2 * 3
2. ;; 前序:
3. + 1 * 2 3    ; => 7
5. ;; 中序: (1 + 2) * 3  
6. ;; 前序:
7. * + 1 2 3   ; => 9

复制代码

而我们现在使用较多的则是后序表达式，因为中序表达式转换为后序表达式内存开销较少，计算更为友好。
2.后序表达式(逆波兰式)

几个逆波兰式的例子：

1. 中序：1 + 2
2. 后序：1 2 +
4. 中序：1 + 2 * 3
5. 后序：1 2 3 * +
7. 中序：(1 + 2) * 3
8. 后序：1 2 + 3 *

复制代码

 
通常可以将表达式从中序转逆序后存放在内存里，供计算时使用。也可以通过双栈法直接计算出结果。
常见的中序转逆序算法如下。
2.1 中序转后序表达式

示例公式：(A + B) * C
首先创建栈结构存放符号
从左向右读取原公式，读到非符号输出，读到符号以如下规则操作：
<ul>若栈为空，读到符号可以直接入栈
* / 优先级高于 + -，将读取到的符号与栈顶符号做比较，若 1,            '*' or '/' => 2,            '(' => 0,    // 左括号在栈内优先级最低            _ => -1      // 其他情况（包括右括号）        };    }    var rpnBuilder = new StringBuilder();    var stack = new Stack();    var numBuilder = new StringBuilder();    foreach (var ch in inStr)    {        if (Char.IsWhiteSpace(ch))        {            // 遇到空格时，如果正在构建数字，就完成这个数字            if (numBuilder.Length > 0)            {                rpnBuilder.Append(numBuilder.ToString()).Append(' ');                numBuilder.Clear();            }            continue;        }        if (char.IsDigit(ch) || ch == '.')        {            // 数字或小数点：添加到数字构建器            numBuilder.Append(ch);            continue;        }        else        {            // 遇到操作符前，先完成当前数字的构建            if (numBuilder.Length > 0)            {                rpnBuilder.Append(numBuilder.ToString()).Append(' ');                numBuilder.Clear();            }        }        switch (ch)        {            case '(':                stack.Push(ch);                break;            case ')':                // 弹出直到遇到左括号                while (stack.Count > 0 && stack.Peek() != '(')                {                    rpnBuilder.Append(stack.Pop()).Append(' ');                }                if (stack.Count > 0 && stack.Peek() == '(')                {                    stack.Pop(); // 弹出左括号但不输出                }                break;            case '+':            case '-':            case '*':            case '/':                // 处理操作符优先级                while (stack.Count > 0 && stack.Peek() != '(' &&                        GetPriority(ch)  0)    {        rpnBuilder.Append(numBuilder.ToString()).Append(' ');    }    // 弹出栈中剩余操作符    while (stack.Count > 0)    {        rpnBuilder.Append(stack.Pop()).Append(' ');    }    // 移除末尾多余的空格    if (rpnBuilder.Length > 0 && rpnBuilder[rpnBuilder.Length - 1] == ' ')    {        rpnBuilder.Length--;    }    rpnStr = rpnBuilder.ToString();}[/code] 这样就可以将公式转换为后序表达式先存放在内存中了。
2.2 求解后序表达式

求解后续表达式，同样需要一个栈结构来辅助。
规则是：

• 遇到操作数（数字/变量） → 压入栈。
  
• 遇到运算符 → 从栈中弹出两个操作数：
  
  
  
  • 先弹出的是右操作数
    
  • 再弹出的是左操作数
    然后进行运算，把结果压回栈。
    
  
  
• 扫描完后，栈顶就是最终结果
  

代码如下：

1. ConvertRpn("1 + 2 * 3 + (4 * e + f) * g", out var rpnStr);
2. Debug.Log(rpnStr);//1 2 3 * + 4 e * f + g * +

复制代码

1. void ConvertRpn(string inStr, out string rpnStr)
2. {
3.     int GetPriority(char ch)
4.     {
5.         return ch switch
6.         {
7.             '+' or '-' => 1,
8.             '*' or '/' => 2,
9.             '(' => 0,    // 左括号在栈内优先级最低
10.             _ => -1      // 其他情况（包括右括号）
11.         };
12.     }
14.     var rpnBuilder = new StringBuilder();
15.     var stack = new Stack<char>();
17.     var numBuilder = new StringBuilder();
19.     foreach (var ch in inStr)
20.     {
21.         if (Char.IsWhiteSpace(ch))
22.         {
23.             // 遇到空格时，如果正在构建数字，就完成这个数字
24.             if (numBuilder.Length > 0)
25.             {
26.                 rpnBuilder.Append(numBuilder.ToString()).Append(' ');
27.                 numBuilder.Clear();
28.             }
29.             continue;
30.         }
32.         if (char.IsDigit(ch) || ch == '.')
33.         {
34.             // 数字或小数点：添加到数字构建器
35.             numBuilder.Append(ch);
36.             continue;
37.         }
38.         else
39.         {
40.             // 遇到操作符前，先完成当前数字的构建
41.             if (numBuilder.Length > 0)
42.             {
43.                 rpnBuilder.Append(numBuilder.ToString()).Append(' ');
44.                 numBuilder.Clear();
45.             }
46.         }
48.         switch (ch)
49.         {
50.             case '(':
51.                 stack.Push(ch);
52.                 break;
54.             case ')':
55.                 // 弹出直到遇到左括号
56.                 while (stack.Count > 0 && stack.Peek() != '(')
57.                 {
58.                     rpnBuilder.Append(stack.Pop()).Append(' ');
59.                 }
60.                 if (stack.Count > 0 && stack.Peek() == '(')
61.                 {
62.                     stack.Pop(); // 弹出左括号但不输出
63.                 }
64.                 break;
66.             case '+':
67.             case '-':
68.             case '*':
69.             case '/':
70.                 // 处理操作符优先级
71.                 while (stack.Count > 0 && stack.Peek() != '(' &&
72.                         GetPriority(ch) <= GetPriority(stack.Peek()))
73.                 {
74.                     rpnBuilder.Append(stack.Pop()).Append(' ');
75.                 }
76.                 stack.Push(ch);
77.                 break;
79.             default:
80.                 rpnBuilder.Append(ch).Append(' ');
81.                 break;
82.         }
83.     }
85.     // 处理最后一个数字（如果存在）
86.     if (numBuilder.Length > 0)
87.     {
88.         rpnBuilder.Append(numBuilder.ToString()).Append(' ');
89.     }
91.     // 弹出栈中剩余操作符
92.     while (stack.Count > 0)
93.     {
94.         rpnBuilder.Append(stack.Pop()).Append(' ');
95.     }
97.     // 移除末尾多余的空格
98.     if (rpnBuilder.Length > 0 && rpnBuilder[rpnBuilder.Length - 1] == ' ')
99.     {
100.         rpnBuilder.Length--;
101.     }
103.     rpnStr = rpnBuilder.ToString();
104. }

复制代码

 
2.3 双栈法直接求值

使用双栈法，可以不用转换为后序表达式再求值，而是直接求值。
核心思想是使用2个栈，数值栈和字符栈。当字符栈弹出时，顺便就计算当前步骤结果并且放回数值栈。
代码如下：

1. rpnStr = "1 2 3 * + 4 e * f + g * +";
2. var result = CalcPrn(rpnStr, new Dictionary<char, float> { ['e'] = 10f, ['f'] = 12f, ['g'] = 14f });
3. Debug.Log(result);// 735

复制代码

1. float CalcPrn(string rpnStr, Dictionary<char, float> replace)
2. {
3.     var rpnBuilder = new StringBuilder();
4.     var stack = new Stack<object>();
6.     var numBuilder = new StringBuilder();
8.     foreach (var ch in rpnStr)
9.     {
10.         if (Char.IsWhiteSpace(ch))
11.         {
12.             if (numBuilder.Length > 0)
13.             {
14.                 stack.Push(float.Parse(numBuilder.ToString()));
15.                 numBuilder.Clear();
16.             }
17.             continue;
18.         }
20.         if (char.IsDigit(ch) || ch == '.')
21.         {
22.             numBuilder.Append(ch);
23.             continue;
24.         }
25.         else
26.         {
27.             if (numBuilder.Length > 0)
28.             {
29.                 stack.Push(float.Parse(numBuilder.ToString()));
30.                 numBuilder.Clear();
31.             }
32.         }
34.         if (ch is '+' or '-' or '*' or '/')
35.         {
36.             var x = (float)stack.Pop();
37.             var y = (float)stack.Pop();
39.             switch (ch)
40.             {
41.                 case '+':
42.                     stack.Push(x + y);
43.                     break;
44.                 case '-':
45.                     stack.Push(x - y);
46.                     break;
47.                 case '*':
48.                     stack.Push(x * y);
49.                     break;
50.                 case '/':
51.                     stack.Push(x / y);
52.                     break;
53.             }
54.         }
55.         else // 变量
56.         {
57.             stack.Push(replace[ch]);
58.         }
59.     }
61.     return (float)stack.Pop();
62. }

复制代码

 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！