C++ 中的后缀表达式转中缀表达式


在这个问题中,我们得到后缀表达式的形式,我们的任务是打印表达式的中缀形式。

中缀表达式是一种操作符位于操作数中间的表达式,例如 操作数 操作符 操作数。

后缀表达式是一种操作符位于操作数之后的表达式,例如 操作数 操作数 操作符。

后缀表达式易于系统计算,但不易于人类阅读。因此需要进行这种转换。通常,最终用户进行阅读和编辑使用中缀表示法,因为它们是用括号分隔的,因此易于人类理解。

让我们举个例子来理解这个问题

输入 − xyz/*

输出 − (x * (y/z))

为了解决这个问题,我们将使用堆栈数据结构。逐一遍历后缀表达式,然后检查以下情况:

情况 1 - 如果找到操作数,则将其压入堆栈。

情况 2 - 如果找到操作符,则弹出两个操作数,创建这三个操作数的中缀表达式,并将该表达式作为操作数压入堆栈。

最后,当堆栈中只剩下一个元素并且遍历完成后,弹出堆栈顶部,这就是中缀转换的结果。

示例

程序演示了我们解决方案的实现。

在线演示

#include <bits/stdc++.h>
using namespace std;
bool isOperand(char x) {
   return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z');
}
string infixConversion(string postfix) {
   stack<string> infix;
   for (int i=0; postfix[i]!='\0'; i++) {
      if (isOperand(postfix[i])) {
         string op(1, postfix[i]);
         infix.push(op);
      } else {
         string op1 = infix.top();
         infix.pop();
         string op2 = infix.top();
         infix.pop();
         infix.push("{"+op2+postfix[i]+op1 +"}");
      }
   }
   return infix.top();
}
int main() {
   string postfix = "xyae+/%";
   cout<<"The infix conversion of the postfix expression '"<<postfix<<"' is : ";
   cout<<infixConversion(postfix);
   return 0;
}

输出

The infix conversion of the postfix expression 'xyae+/%' is : {x%{y/{a+e}}}

更新于:2020年4月17日

5K+ 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告