Postfix to Prefix Conversion & Prefix to Postfix Conversion

Postfix to Prefix Conversion

Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B) * (C-D) )

Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )

Given a Postfix expression, convert it into a Prefix expression.

分析：

• Read the Postfix expression from left to right
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
• Create a string by concatenating the two operands and the operator before them. Like: string = operator + operand2 + operand1, and push the resultant string back to Stack
• Repeat the above steps until end of Prefix expression.

 1 class Solution {
 2     static boolean isOperator(char x) {
 3         switch (x) {
 4             case ‘+‘:
 5             case ‘-‘:
 6             case ‘/‘:
 7             case ‘*‘:
 8                 return true;
 9             default:
10                 return false;
11         }
12     }
13 
14     static String postToPre(String exp) {
15         Stack<String> s = new Stack<>();
16         int length = exp.length();
17         for (int i = 0; i < length; i++) {
18             if (isOperator(exp.charAt(i))) {
19                 String op1 = s.pop();
20                 String op2 = s.pop();
21                 String temp = exp.charAt(i) + op2 + op1;
22                 s.push(temp);
23             }
24             else {
25                 s.push(exp.charAt(i) + "");
26             }
27         }
28         return s.peek();
29     }
30 }

Prefix to Postfix Conversion

Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )

Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B * (C-D) )

Given a Prefix expression, convert it into a Postfix expression.

分析：

• Read the Prefix expression in reverse order (from right to left)
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
• Create a string by concatenating the two operands and the operator after them.
• string = operand1 + operand2 + operator
• And push the resultant string back to Stack
• Repeat the above steps until end of Prefix expression.

 1 class Solution {
 2     boolean isOperator(char x) {
 3         switch (x) {
 4             case ‘+‘:
 5             case ‘-‘:
 6             case ‘/‘:
 7             case ‘*‘:
 8                 return true;
 9             default:
10                 return false;
11         }
12     }
13 
14     String preToPost(String pre_exp) {
15         Stack<String> s = new Stack<>();
16         int length = pre_exp.length();
17         for (int i = length - 1; i >= 0; i--) {
18             if (isOperator(pre_exp.charAt(i))) {
19                 String op1 = s.pop();
20                 String op2 = s.pop();
21                 String temp = op1 + op2 + pre_exp.charAt(i);
22                 s.push(temp);
23             } else {
24                 s.push(pre_exp.charAt(i) + "");
25             }
26         }
27         return s.peek();
28     }
29 }

Postfix to Prefix Conversion & Prefix to Postfix Conversion

原文：https://www.cnblogs.com/beiyeqingteng/p/11318689.html