企业官网建设流程全解析

P1175 表达式的转换

网页链接

P1175 表达式的转换

题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8-(3+2*6)/5+4可以写为：8 3 2 6 * + 5 / - 4 +

其计算步骤为：

8 3 2 6 * + 5 / - 4 + 8 3 12 + 5 / - 4 + 8 15 5 / - 4 + 8 3 - 4 + 5 4 + 9

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

输入格式

就一行，是一个中缀表达式。输入的符号中只有这些基本符号0123456789+-*/^()，并且不会出现负数及形如2*-3的格式。

表达式中的基本数字也都是一位的，不会出现形如12形式的数字。

所输入的字符串不要判错。

输出格式

若干个后缀表达式，第i + 1 i + 1i+1行比第i ii行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

输入输出样例 #1

输入 #1

8-(3+2*6)/5+4

输出 #1

8 3 2 6 * + 5 / - 4 + 8 3 12 + 5 / - 4 + 8 15 5 / - 4 + 8 3 - 4 + 5 4 + 9

输入输出样例 #2

输入 #2

2^2^3

输出 #2

2 2 3 ^ ^ 2 8 ^ 256

说明/提示

运算的结果可能为负数，/为整除运算（向下取整）。并且中间每一步的绝对值都不会超过2 31 2^{31}231。字符串长度不超过100 100100。

注意乘方运算^是从右向左结合的，即2 ^ 2 ^ 3为2 ^ (2 ^ 3)，后缀表达式为2 2 3 ^ ^。

其他同优先级的运算是从左向右结合的，即4 / 2 / 2 * 2为((4 / 2) / 2) * 2，后缀表达式为4 2 / 2 / 2 *。

保证不会出现计算乘方时幂次为负数的情况，故保证一切中间结果为整数。

解题思路

本题是表达式树构建 + 后缀表达式模拟求值的经典问题。要求将中缀表达式转换为后缀表达式，并逐步模拟计算过程，每一步输出当前的后缀表达式，最终输出计算结果。核心在于正确处理运算符优先级、结合性以及括号，并利用表达式树实现逐步求值。

1. 问题等价转化

• 输入一个中缀表达式字符串，只包含数字（一位）、运算符+ - * / ^和括号()。
• 需要先将其转换为后缀表达式（逆波兰式），然后从左到右依次计算，每次计算一个运算符，并将当前表达式输出。这等价于：
  1. 构建一棵表达式二叉树，叶子节点为数字，内部节点为运算符。
  2. 对树进行后序遍历，得到初始后缀表达式。
  3. 每次选择一个内部节点（自底向上），计算其值，将其替换为数字，然后重新后序遍历输出当前后缀表达式，直到根节点计算完毕。
• 注意运算符的优先级和结合性：
  • 优先级：^>* />+ -。
  • 结合性：^是右结合（2^2^3 = 2^(2^3)），其余运算符均为左结合。
• 括号用于改变运算顺序，构建树时需要先去除最外层括号。

2. 算法实现

1. 构建表达式树：

   • 使用递归函数bd(l, r)处理中缀表达式的区间[l, r]。
   • 若l == r，说明是单个数字，创建叶子节点，存储数字。
   • 否则，先检查整个区间是否被一对匹配的括号完全包围（即s[l] == '('且与s[l]匹配的)恰好在r），若是则去掉外层括号，令l++, r--。
   • 从右向左扫描区间，寻找优先级最低的运算符作为当前子树的根。使用变量typo记录当前已找到的最低优先级（初始为 5，数值越小优先级越低）：
     • 遇到+或-，若typo > 1，则更新根位置p = i，typo = 1。
     • 遇到*或/，若typo > 2，则更新p = i，typo = 2。
     • 遇到^，若typo > 3，则更新p = i，typo = 4。
     • 跳过括号内的内容（通过匹配括号快速跳过）。
   • 由于从右向左扫描且只更新一次，对于左结合运算符（+ - * /）会选到最右边的运算符作为根，这恰好对应左结合；对于右结合运算符^，也会选到最右边的^，对应右结合。
   • 创建根节点存储运算符s[p]，递归构建左子树bd(l, p-1)和右子树bd(p+1, r)。
   • 节点信息存储在数组中：v存值（叶子为数字，内部暂存 0），c存运算符或空格（叶子为空格），L和R存左右孩子索引。

2. 输出后缀表达式：

   • 后序遍历函数pr(u)：若c[u]为空格（叶子），输出v[u]；否则先递归左子树，再递归右子树，最后输出运算符c[u]。每个元素后跟一个空格。

3. 逐步模拟计算：

   • 函数df(x)：递归地计算以x为根的子树。
     • 若x是叶子（c[x] == ' '），直接返回。
     • 否则先递归计算左右子树df(L[x])和df(R[x])。
     • 计算当前节点的值：根据运算符c[x]和左右孩子的值v[L[x]], v[R[x]]进行计算（注意/为整除，向下取整；^用快速幂或pow计算，但需保证整数）。
     • 将计算结果存入v[x]，并将c[x]置为空格（表示已计算）。
     • 调用pr(1)输出当前整个表达式的后缀形式，并换行。
   • 从根节点调用df(1)，最终所有节点计算完毕，最后一行输出结果。

3. 复杂度分析

• 时间复杂度：构建表达式树需要O ( L 2 ) O(L^2)O(L2)最坏（每次扫描区间），但字符串长度L ≤ 100 L \le 100L≤100，完全可忽略。后续每次计算一个节点并输出整个后缀表达式，输出总长度约为O ( L 2 ) O(L^2)O(L2)，整体运算量极小。
• 空间复杂度：表达式树节点数O ( L ) O(L)O(L)，辅助数组O ( L ) O(L)O(L)，空间消耗极低。

总结

通过将中缀表达式构建为表达式树，利用后序遍历得到后缀表达式，并自底向上逐步计算内部节点，每次计算后重新输出当前后缀表达式，完美模拟了题目要求的转换和求值过程。正确处理运算符优先级、结合性和括号是构建树的关键，而从右向左扫描并选择最低优先级运算符作为根的方法巧妙实现了左结合和右结合的统一。

代码简要说明

• 全局数组：s存中缀表达式，c[N]存节点运算符（空格表示数字），v[N]存节点值，L[N], R[N]存左右孩子索引，t为节点计数器。
• bd(l, r)：递归构建表达式树。先处理外层括号，再从右向左扫描找根运算符（优先级最低，相同优先级取最右），递归构建左右子树。
• pr(u)：后序遍历输出后缀表达式。
• cc(a, b, op)：根据运算符计算a op b，/为整除，^用pow。
• df(x)：递归计算子树，先计算左右孩子，再计算当前节点，更新v[x]和c[x]，然后输出当前后缀表达式。
• 主函数：读入字符串，调用bd(0, len-1)建树，输出初始后缀表达式，然后调用df(1)逐步计算并输出。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=114514;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;string s;charc[N];ll v[N],L[N],R[N],t=0;voidbd(ll l,ll r){if(l==r){v[++t]=s[l]-'0';c[t]=' ';return;}if(s[l]=='('){ll go=1;for(ll i=l+1;i<=r;i++){if(s[i]=='(')go++;elseif(s[i]==')')go--;if(go==0){if(i==r)l++,r--;break;}}}ll p,typo=5;for(ll i=r;i>=l;i--){if(s[i]==')'){ll go=1,j;for(j=i-1;j>=l;j--){if(s[j]==')')go++;elseif(s[j]=='(')go--;if(go==0)break;}i=j;continue;}elseif(s[i]<='9'&&s[i]>='0')continue;else{if((s[i]=='+'||s[i]=='-')&&typo>1){p=i;typo=1;}elseif((s[i]=='*'||s[i]=='/')&&typo>2){p=i;typo=2;}elseif(s[i]=='^'&&typo>3){p=i;typo=4;}}}ll x=++t;c[x]=s[p];L[x]=t+1;bd(l,p-1);R[x]=t+1;bd(p+1,r);}llcc(ll a,ll b,chargk){switch(gk){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':returna/b;case'^':returnpow(a,b);}return0;}voidpr(ll u){if(c[u]==' '){cout<<v[u]<<" ";return;}pr(L[u]);pr(R[u]);cout<<c[u]<<" ";}voiddf(ll x){if(c[x]==' ')return;df(L[x]);df(R[x]);v[x]=cc(v[L[x]],v[R[x]],c[x]);c[x]=' ';pr(1);cout<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>s;bd(0,s.size()-1);pr(1);cout<<endl;df(1);return0;}