后缀表达式：如果一个表达式中的运算符出现在操作数之后，我们称之为后缀表达式。简单来说，其形式为 (操作数1 操作数2 运算符)。
示例 : AB+CD- (对应中缀表达式 : (A+B) (C-D) )
前缀表达式：如果一个表达式中的运算符出现在操作数之前，我们称之为前缀表达式。简单来说，其形式为 (运算符 操作数1 操作数2)。
示例 : +AB-CD (对应中缀表达式 : (A+B) (C-D) )
问题陈述
给定一个 后缀表达式，将其转换为 前缀表达式。
我们不需要像传统方法那样先转换为中缀表达式（即 后缀 → 中缀 → 前缀），我们可以直接将 后缀转换为前缀。
这种方法不仅高效（步骤更少），而且非常直观，因为计算机在处理表达式时本质上就是以后缀形式运行的。
示例：
> 输入 : 后缀表达式 : AB+CD-*
> 输出 : 前缀表达式 : *+AB-CD
> 解释 : 后缀转中缀 : (A+B) * (C-D)
> 中缀转前缀 : *+AB-CD
>
> 输入 : 后缀表达式 : ABC/-AK/L-*
> 输出 : 前缀表达式 : *-A/BC-/AKL
> 解释 : 后缀转中缀 : ((A-(B/C))*((A/K)-L))
> 中缀转前缀 : *-A/BC-/AKL
后缀转前缀的算法：
让我们使用一个 栈（Stack） 来逐步构建前缀表达式：
- 从左到右读取后缀表达式
- 如果符号是操作数，则将其压入栈中
- 如果符号是运算符，则从栈中弹出两个操作数
通过将运算符放在两个操作数之前来拼接成一个字符串。
字符串 = 运算符 + 操作数2 + 操作数1
并将结果字符串压回栈中
- 重复上述步骤，直到到达后缀表达式的末尾。
下面是上述算法的实现：
C++
CODEBLOCK_fd8359c4
Java
// Java Program to convert postfix to prefix
import java.util.*;
class GFG {
// function to check if character
// is operator or not
static boolean isOperator(char x)
{
switch (x) {
case ‘+‘:
case ‘-‘:
case ‘/‘:
case ‘*‘:
return true;
}
return false;
}
// Convert postfix to Prefix expression
static String postToPre(String post_exp)
{
Stack s = new Stack();
// length of expression
int length = post_exp.length();
// reading from right to left
for (int i = 0; i < length; i++) {
// check if symbol is operator
if (isOperator(post_exp.charAt(i))) {
// pop two operands from stack
String op1 = s.peek();
s.pop();
String op2 = s.peek();
s.pop();
// concat the operands and operator
String temp
= post_exp.charAt(i) + op2 + op1;
// Push String temp back to stack
s.push(temp);
}
// if symbol is an operand
else {
// push the operand to the stack
s.push(post_exp.charAt(i) + "");
}
}
// concatenate all strings in stack and return the
// answer
String ans = "";
for (String i : s)
ans += i;
return ans;
}
// Driver Code
public static void main(String args[])
{
String post_exp = "ABC/-AK/L-*";
// Function ca