Infix to Prefix conversion using two stacks
Infix?: An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2). 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). Given an Infix expression,convert it into a Prefix expression using two stacks. Examples: Input : A * B + C / D Output : + * A B/ C D Input : (A - B/C) * (A/K-L) Output : *-A/BC-/AKL
1 class Solution { 2 boolean isOperator(char C) { 3 return C == ‘-‘ || C == ‘+‘ || C == ‘*‘ || C == ‘/‘ || C == ‘^‘; 4 } 5 6 int getPriority(char C) { 7 if (C == ‘-‘ || C == ‘+‘) { 8 return 1; 9 } else if (C == ‘*‘ || C == ‘/‘) { 10 return 2; 11 } else if (C == ‘^‘) { 12 return 3; 13 } else { 14 return 0; 15 } 16 } 17 String infixToPrefix(String infix) { 18 Stack<Character> operators = new Stack<>(); 19 Stack<String> operands = new Stack<String>(); 20 21 for (int i = 0; i < infix.length(); i++) { 22 if (infix.charAt(i) == ‘(‘) { 23 operators.push(infix.charAt(i)); 24 } 25 else if (infix.charAt(i) == ‘)‘) { 26 while (!operators.empty() && operators.peek() != ‘(‘) { 27 String op1 = operands.pop(); 28 String op2 = operands.pop(); 29 30 char op = operators.pop(); 31 String tmp = op + op2 + op1; 32 operands.push(tmp); 33 } 34 } else if (!isOperator(infix.charAt(i))) { 35 operands.push(infix.charAt(i) + ""); 36 } 37 else { 38 while (!operators.empty() && getPriority(infix.charAt(i)) <= getPriority(operators.peek())) { 39 String op1 = operands.pop(); 40 String op2 = operands.pop(); 41 42 char op = operators.pop(); 43 operands.push(op + op2 + op1); 44 } 45 operators.push(infix.charAt(i)); 46 } 47 } 48 49 while (!operators.empty()) { 50 String op1 = operands.pop(); 51 String op2 = operands.pop(); 52 53 char op = operators.pop(); 54 operands.push(op + op2 + op1); 55 } 56 return operands.peek(); 57 } 58 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |