C++ 中的前缀转后缀转换

在此问题中，给出了一个前缀表达式。我们的任务是打印该表达式的后缀转换。

前缀表达式是操作符位于操作数之前的表达式。

例如：+AB。

后缀表达式是操作符位于表达式中操作数之后的表达式。

例如：AB/

不要将前缀转换为后缀时涉及转换为中缀。

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

Input: /+XY+NM
Output: XY+NM+/
Explanation: infix -> (X+Y)/(N+M)

为了解决此问题，我们首先以相反的顺序遍历整个后缀表达式。并且，我们将使用堆栈数据结构来进行我们的处理。对于遍历中找到的元素情况，执行以下操作

情况：如果符号是操作数 -> 将元素压入堆栈中。

情况：如果符号是操作符 -> 从堆栈中弹出 2*，然后将操作数 - 操作数 - 操作符序列压入。

显示我们算法实现的程序

示例

 在线演示

#include <iostream>
#include <stack>
using namespace std;
bool isOperator(char x) {
   switch (x) {
      case '+':
      case '-':
      case '/':
      case '*':
      return true;
   }
   return false;
}
string convertToPostfix(string prefix) {
   stack<string> expression;
   int length = prefix.size();
   for (int i = length - 1; i >= 0; i--) {
      if (isOperator(prefix[i])) {
         string op1 = expression.top();
         expression.pop();
         string op2 = expression.top();
         expression.pop();
         string temp = op1 + op2 + prefix[i];
         expression.push(temp);
      }
      else
         expression.push(string(1, prefix[i]));
   }
   return expression.top();
}
int main() {
   string prefix = "*-AB/+CD*XY";
   cout<<"Prefix expression : "<<prefix<<endl;
   cout<<"Postfix expression : "<<convertToPostfix(prefix);
   return 0;
}

输出

Prefix expression : *-AB/+CD*XY
Postfix expression : AB-CD+XY*/*

更新日期：03-Feb-2020

3K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始吧
广告