1.Revert infix to postfix
public class Solution { public static String infixToPostfix(String infix){ if(infix == null || infix.length() == 0){ throw new IllegalArgumentException("wrong input"); } Stack<Character> table = new Stack<Character>(); StringBuilder res = new StringBuilder(); for(int i=0; i<infix.length(); i++){ if(infix.charAt(i) == '('){ table.push(infix.charAt(i)); continue; }else if(infix.charAt(i) == '+' || infix.charAt(i) == '-' || infix.charAt(i) == '*' || infix.charAt(i) == '/'){ while(!table.isEmpty() && getPriority(infix.charAt(i)) <= getPriority(table.peek())){ res.append(table.pop()); } table.push(infix.charAt(i)); }else if(infix.charAt(i) == ')'){ while(table.peek() != '('){ res.append(table.pop()); if(table.isEmpty()){ throw new IllegalArgumentException("wrong input"); } } table.pop(); }else{ res.append(infix.charAt(i)); } } while(!table.isEmpty()){ res.append(table.pop()); } return res.toString(); } private static int getPriority(Character cur){ if(cur == '+' || cur == '-'){ return 1; }else{ return 2; } } public static void main(String[] args){ System.out.println(infixToPostfix("1+2*3-4")); System.out.println(infixToPostfix("1/2*3-4")); System.out.println(infixToPostfix("1*2-3/4")); System.out.println(infixToPostfix("1-2+3*4")); } }
NO.2 calculate Profix
Using stack:
public class Solution { public int evalRPN(String[] tokens) { if(tokens == null || tokens.length == 0){ throw new IllegalArgumentException("wrong input"); } Stack<String> nums = new Stack<String>(); for(int i=0; i<tokens.length; i++){ if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*")|| tokens[i].equals("/")){ if(nums.isEmpty()){ throw new IllegalArgumentException("wrong input"); } String b = nums.pop(); if(nums.isEmpty()){ throw new IllegalArgumentException("wrong input"); } String a = nums.pop(); nums.push(cal(a,b,tokens[i])); }else{ nums.push(tokens[i]); } } if(nums.size() != 1){ throw new IllegalArgumentException("wrong input"); } return Integer.valueOf(nums.pop()); } private String cal(String a, String b, String op){ switch(op){ case "+" : return String.valueOf(Integer.valueOf(a)+Integer.valueOf(b)); case "-" : return String.valueOf(Integer.valueOf(a)-Integer.valueOf(b)); case "*" : return String.valueOf(Integer.valueOf(a)*Integer.valueOf(b)); default : return String.valueOf(Integer.valueOf(a)/Integer.valueOf(b)); } }}
NO.3 convert Profix to binary tree:
public class Solution { public TreeNode postfixToBST(String postFix){ if(postFix == null || postFix.isEmpty()){ throw new IllegalArgumentException("wrong input"); } Stack<TreeNode> nods = new Stack<TreeNode>(); for(int i = 0; i<postFix.length(); i++){ if(postFix.charAt(i)>='0' && postFix.charAt(i)<= '9'){ nods.push(new TreeNode(postFix.charAt(i))); }else{ TreeNode node2 = nods.pop(); TreeNode node1 = nods.pop(); nods.push(new TreeNode(postFix.charAt(i), node1, node2)); } } if(nods.size() != 1){ throw new IllegalArgumentException("wrong input"); } return nods.pop(); }}
NO.4 calculate Profix binary tree:
public int calculatePostfixTree(TreeNode root){ if(root == null){ throw new IllegalArgumentException("wrong input"); } if(root.left == null && root.right == null){ return root.lable - '0'; }else{ return cal(calculatePostfixTree(root.left), root.lable, calculatePostfixTree(root.right)); } } private int cal(int left, char root, int right){ switch(root){ case '+' : return left + right; case '-' : return left - right; case '*' : return left * right; default : return left / right; } }
NO.5 Convert Profix to infix:
public class Solution{
//http://www.codeproject.com/Articles/405361/Converting-Postfix-Expressions-to-Infix
// !!! Assume: the postfix expression to be processed is comma-delimited.
public String convertPostFixtoInFix(String postFix){
String[] arr = postFix.split( ",");
Stack<Expression> st = new Stack<Expression>();
for(int i=0; i<arr.length; i++){
if(arr[i].equals("+" ) || arr[i].equals("-")){
if(st.size()<2){
throw new IllegalArgumentException("wrong input");
}
Expression rightExpression = st.pop();
Expression leftExpression = st.pop();
st.push( new Expression(leftExpression.expression + arr[i] + rightExpression.expression , arr[i]));
} else if (arr[i].equals("*") || arr[i].equals( "/")){
if(st.size()<2){
throw new IllegalArgumentException("wrong input");
}
Expression rightExpression = st.pop();
if(rightExpression.operator .equals("+" ) || rightExpression.operator.equals("-" )){
rightExpression. expression = "(" + rightExpression.expression + ")" ;
}
Expression leftExpression = st.pop();
if(leftExpression.operator .equals("+" ) || leftExpression.operator.equals("-" )){
leftExpression. expression = "(" + leftExpression.expression+ ")" ;
}
st.push( new Expression(leftExpression.expression + arr[i] + rightExpression.expression , arr[i]));
//!! attension : use leftExpression.expression, instead of leftExpression
} else{
st.push( new Expression(arr[i], "" ));
}
}
if(st.size() != 1){
throw new IllegalArgumentException("wrong input");
}
return st.pop().expression ;
}
private class Expression{
private String expression ;
private String operator ;
private Expression(String expr, String oper){
this.expression = expr;
this.operator = oper;
}
}
}
public class Test {
public static void main(String[] args){
Solution so = new Solution();
System. out.println();
System. out.println(so.convertPostFixtoInFix("a,b,+,c,/" ));
System. out.println(so.convertPostFixtoInFix("1,2,3,*,+" ));
System. out.println(so.convertPostFixtoInFix("1,2,*,3,4,*,+,5,*" ));
}
}