Originally Posted by
jairoh_
cge bro. tnx ha, pls butangi ug mga comments, kai gusto ko makasabot.
hmm. sakto mana akong prefix manually bro. PMDAS man, pero dili tanto kai pareha raman ug value ang addition ug subtraction, also division and multiplication. so left to right kung addition/subtraction, same sad sa multiplication/division. mao sad na ang gihatag samu instructor.
unsa na imo editor bro?
mao ba bro, hehe wa nko gisubay ug maau ang infix notation, ako ra gi-assume nga kung i-reverse ang postfix kay mao na na ang prefix, pag-test nko sa 4 prefix examples nimo kay ok man siya sa last 2 examples - same result pero lahi na ang resulta sa 1st ug 2nd... then i googled, pwede diay daghan klase pagkasulat sa prefix notation 
Code:
(4 + 5) * 6
is equal to
* 6 + 4 5
or
* + 4 5 6
source: http://www.hpmuseum.org/rpn.htm
anyway para mka-sure ta, palihug verify kung equal ba ni nga results...
Code:
(300 + 23) * (43 - 21) / (84 + 7)
is equal to
/ * + 300 23 - 43 21 + 84 7 (imoha)
or
* + 300 23 / - 43 21 + 84 7 (akoa)
ug kani pud...
Code:
(60 * 4) + (43 - 21) - (44 + 7)
is equal to
- + * 60 4 - 43 21 + 44 7 (imoha)
or
+ * 60 4 - - 43 21 + 44 7 (akoa)
nia ra ang code bro..
Code:
// filename: Notation.java
import java.util.Scanner;
import java.util.Stack;
public class Notation {
public static final int PREFIX = 1;
public static final int POSTFIX = 2;
private static final String OPEN_BRACKET = "([{";
private static final String CLOSE_BRACKET = "}])";
private static final String WHITESPACE = "\n\t ";
private static final String OPERATOR = "*/+-";
private static final String MISSING_BRACKET = "%s %s IS MISSING.";
private static final String INVALID_CHARACTER = "INVALID CHARACTER AT INDEX %d.";
private boolean postfix;
private String buffer;
private String output;
private Stack<String> stack = new Stack<String>();
public String toString() {
return output.trim();
}
public boolean build(String expression, int notation) {
postfix = notation == POSTFIX;
buffer = "";
output = "";
stack.clear();
int length = expression.length();
int index = postfix ? 0 : length - 1;
while (postfix ? index < length : index >= 0) {
String token = expression.substring(index, index + 1);
if (OPEN_BRACKET.contains(token)) {
if (postfix) {
stack.push(token);
} else {
if (!seekBracket(token)) {
return false;
}
}
} else if (CLOSE_BRACKET.contains(token)) {
if (postfix) {
if (!seekBracket(token)) {
return false;
}
} else {
stack.push(token);
}
} else if (OPERATOR.contains(token)) {
flushBuffer();
while (!stack.empty() && OPERATOR.contains(stack.peek()) && getPrecedence(token) <= getPrecedence(stack.peek())) {
output = postfix ? output + " " + stack.pop() : " " + stack.pop() + output;
}
stack.push(token);
} else if (Character.isDigit(token.charAt(0)) || Character.isLetter(token.charAt(0))) {
buffer = postfix ? buffer + token : token + buffer;
} else if (!WHITESPACE.contains(token)) {
output = String.format(INVALID_CHARACTER, (index + 1));
return false;
}
index += postfix ? 1 : -1;
}
flushBuffer();
while (!stack.empty()) {
String token = stack.peek();
if ((postfix ? OPEN_BRACKET : CLOSE_BRACKET).contains(token)) {
output = String.format(MISSING_BRACKET, OPEN_BRACKET.contains(token) ? "CLOSE" : "OPEN", getBracketName(token));
return false;
}
output = postfix ? output + " " + stack.pop() : stack.pop() + output;
}
return true;
}
private boolean seekBracket(String token) {
flushBuffer();
while (!stack.empty() && !(postfix ? OPEN_BRACKET : CLOSE_BRACKET).contains(stack.peek())) {
output = postfix ? output + " " + stack.pop() : " " + stack.pop() + output;
}
if (stack.empty()) {
output = String.format(MISSING_BRACKET, CLOSE_BRACKET.contains(token) ? "OPEN" : "CLOSE", getBracketName(token));
return false;
}
stack.pop();
return true;
}
private void flushBuffer() {
if (!buffer.isEmpty()) {
output = postfix ? output + " " + buffer : " " + buffer + output;
buffer = "";
}
}
private String getBracketName(String bracket) {
return "()".contains(bracket) ? "PARENTHESIS" : "{}".contains(bracket) ? "BRACE" : "BRACKET";
}
private int getPrecedence(String operator) {
return "*/".contains(operator) ? 3 : "+-".contains(operator) ? 2 : 0;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
boolean done = false;
while (!done) {
System.out.println("------------ MENU ------------");
System.out.println("[1] CONVERT INFIX TO PREFIX.");
System.out.println("[2] CONVERT INFIX TO POSTFIX.");
System.out.println("[3] QUIT PROGRAM.\n");
System.out.print("SELECT FROM MENU [1-3] : ");
String input = scan.nextLine();
if (!input.isEmpty()) {
char selection = input.trim().charAt(0);
switch (selection) {
case '1' :
case '2' :
System.out.print("\nINPUT EXPRESSION USING INFIX NOTATION : ");
String expression = scan.nextLine();
if (!expression.trim().isEmpty()) {
Notation notation = new Notation();
String type = (selection == '1' ? "PREFIX" : "POSTFIX");
if (notation.build(expression, (int) selection - '0')) {
System.out.println("OUTPUT EXPRESSION IN " + type + " NOTATION : " + notation + "\n");
} else {
System.out.println("INFIX EXPRESSION PARSE ERROR. " + notation + "\n");
}
System.out.print("PRESS ENTER TO CONTINUE...");
scan.nextLine();
} else {
System.out.println("EXPRESSION IS EMPTY.");
}
break;
case '3' :
done = true;
break;
default :
input = "";
break;
}
}
if (input.isEmpty()) {
System.out.println("INVALID SELECTION. PLEASE TRY AGAIN.");
}
System.out.println();
}
System.out.println("GOODBYE!");
}
}
sample output:
Code:
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 1
INPUT EXPRESSION USING INFIX NOTATION : (60*4)+(43-21)*(44+7)
OUTPUT EXPRESSION IN PREFIX NOTATION : + * 60 4 * - 43 21 + 44 7
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 1
INPUT EXPRESSION USING INFIX NOTATION : 12+(2-7)
OUTPUT EXPRESSION IN PREFIX NOTATION : + 12 - 2 7
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : (300+23)*(43-21)/(84+7)
OUTPUT EXPRESSION IN POSTFIX NOTATION : 300 23 + 43 21 - * 84 7 + /
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : (60*4)+(43-21)-(44+7)
OUTPUT EXPRESSION IN POSTFIX NOTATION : 60 4 * 43 21 - + 44 7 + -
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : (60*4)+(43-21)*(44+7)
OUTPUT EXPRESSION IN POSTFIX NOTATION : 60 4 * 43 21 - 44 7 + * +
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : 12+(2-7)
OUTPUT EXPRESSION IN POSTFIX NOTATION : 12 2 7 - +
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : 123 * abc / 4
OUTPUT EXPRESSION IN POSTFIX NOTATION : 123 abc * 4 /
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : (1 + 2 * 3
INFIX EXPRESSION PARSE ERROR. CLOSE PARENTHESIS IS MISSING.
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : 1 + 3] * 3
INFIX EXPRESSION PARSE ERROR. OPEN BRACKET IS MISSING.
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : (1 + 2 * [3 - 4]) / 3
OUTPUT EXPRESSION IN POSTFIX NOTATION : 1 2 3 4 - * + 3 /
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 2
INPUT EXPRESSION USING INFIX NOTATION : $1 + 2
INFIX EXPRESSION PARSE ERROR. INVALID CHARACTER AT INDEX 1.
PRESS ENTER TO CONTINUE...
------------ MENU ------------
[1] CONVERT INFIX TO PREFIX.
[2] CONVERT INFIX TO POSTFIX.
[3] QUIT PROGRAM.
SELECT FROM MENU [1-3] : 3
GOODBYE!
* it can handle nested brackets, ex. (1 + 2 * [3 - 4]) / 3
* it can handle different types of brackets, (), [], {} but for now synonymous ra ang tanan nga opening ug closing brackets
* basic nga runtime error handling. ex. kung di balance ang brackets kay mo-report siya unsay missing, or naa ba run invalid characters sa input kay pahibaw-on niya ang user
* it can handle whitespaces, ex. new lines, spaces, tabs. gamit ni para pwede naay space sa input
* it can handle constants and variables, ex. a + b * c, 1 + 2 * 3, 123 * abc / 4
* same method ra ang prefix ug postfix, no redundant code, single pass
* stack ug scanner ray gi-import
* dali ra i-extend to support other operators, ex. =, ^, %, &, |, etc.
* wa nko mabutangan ug comments kay dinalian. karon ra pud ko nabakante ug balik. ok ra man tingali kung diri na lang ya ta mag-comment2x
about sa akong editor kay it depends kung unsay buhaton... kung ginagmay ra nga code parehas ani kay vim or geany akong gamiton. kung dako ang project kay eclipse.
Re: JAVA. help in data structures(algorithm)
Reply With Quote
Posting Permissions
