当前位置: 首页 > news >正文

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

在游戏开发中,我们经常需要在配置表中定义各种公式,比如 a * (b + c),用来计算技能伤害、属性加成等。如果直接让程序在运行时解析并执行这些公式,就需要处理运算符优先级和括号等复杂问题。

这时,后序表达式就派上了用场。我们将中序表达式 a * (b + c) 转换为后序表达式 a b c + *,这样程序只需要一个栈就能高效计算,无需担心优先级和括号。

而要深入理解后序表达式,就不得不提到与之相关的完整概念体系:前序表达式、中序表达式和后序表达式。这三种表达式各有特点,共同构成了计算机处理数学表达式的理论基础。

 

1.中序(中缀)&前序表达式

中序表达式就是日常书写的公式,但这种日常公式对计算机并不友好,有括号、优先级等需要考虑,计算机直接读取较为麻烦

因此波兰数学家扬·武卡谢维奇发明了"波兰表示法"(前序表达式)

所以前序表达式又叫做 波兰式

 

例如LISP的语法风格就是基于前序表达式的:

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

而我们现在使用较多的则是后续表达式,因为中序表达式转换为后续表达式内存开销较少,计算更为友好。

2.后序表达式(逆波兰式)

几个逆波兰式的例子:

中序:1 + 2
后序:1 2 +中序:1 + 2 * 3
后序:1 2 3 * +中序:(1 + 2) * 3
后序:1 2 + 3 *

 

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

常见的中序转逆序算法如下。

2.1 中序转后序表达式

示例公式:(A + B) * C

首先创建栈结构存放符号

从左向右读取原公式,读到非符号输出,读到符号以如下规则操作:

  • 若栈为空,读到符号可以直接入栈
  • * / 优先级高于 + -,将读取到的符号与栈顶符号做比较,若<=栈顶符号,则出栈(循环操作,直到条件不满足),并输出
  • 若读取到左括号(,则连同括号一起入栈。若读取到右括号),则循环出栈,直到找到左括号位置
  • 若所有内容读取完,则输出栈的内容

注:输出是指将值添加至返回值字符串或其他数据格式

 

参照上面写的示例公式,操作流程如下:

  1. (  入栈
    栈:(
    输出:空

  2. A  输出
    输出:A

  3. +  入栈
    栈:(, +
    输出:A

  4. B 输出
    输出:A B

  5. ) 弹出直到遇到 ( → 弹出 +
    栈:空
    输出:A B +

  6. * 栈空 , 入栈
    栈:*
    输出:A B +

  7. C 输出
    输出:A B + C

结束后弹栈:输出 A B + C *

 

通常游戏配表中的公式可运用到此方法,以带变量公式为例,进行代码演示

1 + 2 * 3 + (4 * e + f) * g

 

代码如下:

ConvertRpn("1 + 2 * 3 + (4 * e + f) * g", out var rpnStr);
Debug.Log(rpnStr);//1 2 3 * + 4 e * f + g * +
void ConvertRpn(string inStr, out string rpnStr)
{int GetPriority(char ch){return ch switch{'+' or '-' => 1,'*' or '/' => 2,'(' => 0,    // 左括号在栈内优先级最低_ => -1      // 其他情况(包括右括号)
        };}var rpnBuilder = new StringBuilder();var stack = new Stack<char>();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) <= GetPriority(stack.Peek())){rpnBuilder.Append(stack.Pop()).Append(' ');}stack.Push(ch);break;default:rpnBuilder.Append(ch).Append(' ');break;}}// 处理最后一个数字(如果存在)if (numBuilder.Length > 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();
}

 这样就可以将公式转换为后序表达式先存放在内存中了。

2.2 求解后序表达式

求解后续表达式,同样需要一个栈结构来辅助。

规则是:

    1. 遇到操作数(数字/变量) → 压入栈。

    2. 遇到运算符 → 从栈中弹出两个操作数:

      • 先弹出的是右操作数

      • 再弹出的是左操作数
        然后进行运算,把结果压回栈。

    3. 扫描完后,栈顶就是最终结果

代码如下:

rpnStr = "1 2 3 * + 4 e * f + g * +";
var result = CalcPrn(rpnStr, new Dictionary<char, float> { ['e'] = 10f, ['f'] = 12f, ['g'] = 14f });
Debug.Log(result);// 735
float CalcPrn(string rpnStr, Dictionary<char, float> replace)
{var rpnBuilder = new StringBuilder();var stack = new Stack<object>();var numBuilder = new StringBuilder();foreach (var ch in rpnStr){if (Char.IsWhiteSpace(ch)){if (numBuilder.Length > 0){stack.Push(float.Parse(numBuilder.ToString()));numBuilder.Clear();}continue;}if (char.IsDigit(ch) || ch == '.'){numBuilder.Append(ch);continue;}else{if (numBuilder.Length > 0){stack.Push(float.Parse(numBuilder.ToString()));numBuilder.Clear();}}if (ch is '+' or '-' or '*' or '/'){var x = (float)stack.Pop();var y = (float)stack.Pop();switch (ch){case '+':stack.Push(x + y);break;case '-':stack.Push(x - y);break;case '*':stack.Push(x * y);break;case '/':stack.Push(x / y);break;}}else // 变量
        {stack.Push(replace[ch]);}}return (float)stack.Pop();
}

 

2.3 双栈法直接求值

使用双栈法,可以不用转换为后序表达式再求值,而是直接求值。

核心思想是使用2个栈,数值栈和字符栈。当字符栈弹出时,顺便就计算当前步骤结果并且放回数值栈。

代码如下:

var result = CalcPrnDoubleStack("1 + 2 * 3 + (4 * e + f) * g", new Dictionary<char, float> { ['e'] = 10f, ['f'] = 12f, ['g'] = 14f });
Debug.Log(result);// 735
 float CalcPrnDoubleStack(string inStr, Dictionary<char, float> replace){int GetPriority(char ch){return ch switch{'+' or '-' => 1,'*' or '/' => 2,'(' => 0,    // 左括号在栈内优先级最低_ => -1      // 其他情况(包括右括号)
         };}float Calc(float x, float y, char token){return token switch{'+' => x + y,'-' => x - y,'*' => x * y,'/' => x / y,_ => default};}var stackNum = new Stack<float>();var stackToken = new Stack<char>();var numBuilder = new StringBuilder();foreach (var ch in inStr){if (Char.IsWhiteSpace(ch)){// 遇到空格时,如果正在构建数字,就完成这个数字if (numBuilder.Length > 0){stackNum.Push(float.Parse(numBuilder.ToString()));numBuilder.Clear();}continue;}if (char.IsDigit(ch) || ch == '.'){// 数字或小数点:添加到数字构建器
             numBuilder.Append(ch);continue;}else{// 遇到操作符前,先完成当前数字的构建if (numBuilder.Length > 0){stackNum.Push(float.Parse(numBuilder.ToString()));numBuilder.Clear();}}switch (ch){case '(':stackToken.Push(ch);break;case ')':while (stackToken.Count > 0 && stackToken.Peek() != '('){var token = stackToken.Pop();var y = stackNum.Pop();var x = stackNum.Pop();stackNum.Push(Calc(x, y, token));}stackToken.Pop();break;case '+':case '-':case '*':case '/':while (stackToken.Count > 0 && stackToken.Peek() != '(' &&GetPriority(ch) <= GetPriority(stackToken.Peek())){var token = stackToken.Pop();var y = stackNum.Pop();var x = stackNum.Pop();stackNum.Push(Calc(x, y, token));}stackToken.Push(ch);break;default:stackNum.Push(replace[ch]);break;}}while (stackToken.Count > 0){var token = stackToken.Pop();var y = stackNum.Pop();var x = stackNum.Pop();stackNum.Push(Calc(x, y, token));}return stackNum.Pop();}

 

http://www.hskmm.com/?act=detail&tid=15869

相关文章:

  • flink书籍 - --
  • 详述大模型备案
  • Asp.Net Core 鉴权授权
  • 124
  • 我的笔记记录方案
  • AT_arc156_d [ARC156D] Xor Sum 5
  • iOS Provisioning Profile 证书 描述文件
  • 计算快速付氏变换FFT前需要加窗函数
  • 直播预告| PostgreSQL 与 IvorySQL 在云原生时代的演进与实践
  • KGDB(Kernel GNU Debugger)工具使用方法详解 - 详解
  • Wallpaper Engine v2.7.3 动态壁纸软件-内含数百款动态皮肤 - 实践
  • 力扣155题 最小栈
  • Markdown语法
  • 压垮项目经理的“三座大山”:时间、成本、质量的生存法则与破局工具
  • 最新微信机器人开发教程
  • 金蝶AAS (Apusic Application Server) v10 部署SuperMap iServer 2025 详细教程
  • AI智能会话原型解析:知识问答与知识库管理的设计思路(附模版)
  • Linux - Nginx 文件访问403 forbidden = 授权 chmod -R 777 文件名称
  • 爬虫逆向--Day25Day26--原型链补环境
  • 阻抗匹配技术:信号完整性与功率传输的基石​​
  • 萝卜视频小程序管理系统:多场景适配的短视频商业解决方案
  • 栈与队列专题
  • 读书笔记:为什么你的索引“罢工”了?六种常见原因解析
  • 平面网格材质
  • OSCP备考成功指南:9大实用学习技巧
  • 设备租赁系统:建材租赁行业的高效管理解决方案
  • NOI 2025 题解
  • 迈特海外短剧多语言版 SAAS 开源系统:助力短剧出海,开启全球盈利新赛道
  • 临时测试php文件
  • csv文件中的空行问题