Witam,
Napisałem konwerter wrażeń z postaci infixowej<->postfixowej, który niestety nie przechodzi testów (do których nie mam wglądu). Wykorzystuję własną implementację tablicową stosu, zgodnie z założeniami jakie mają być spełnione.
Konwersję do ONP rozwiązałem na podstawie wiki: http://pl.wikipedia.org/wiki/ONP#Algorytm_konwersji_z_notacji_infiksowej_do_ONP, przy czym zakładam, że dla operatorów o tym samym priorytecie, są one lewostronnie łączne.
Konwersję z ONP wykonuję na stosie na którym układam węzły drzewa.
/**
* Klasa metod pomocniczych dla konwerrrrrsji Infix-Postfix
*/
class Recognition {
public boolean isLetter(String symbol) {
return symbol.matches("[a-zA-Z]");
}
public boolean isOperator(String s) {
if (s.equals("+")
|| s.equals("-")
|| s.equals("*")
|| s.equals("/")
|| s.equals("^")
|| s.equals("~")) {
return true;
} else {
return false;
}
}
public boolean isOpenBracket(String symbol) {
return (symbol.equals("(")) ? true : false;
}
public boolean isCloseBracket(String symbol) {
return (symbol.equals(")")) ? true : false;
}
public int getPriority(String symbol) {
char temp = symbol.charAt(0);
switch (temp) {
case '+': {
return 1;
}
case '-': {
return 1;
}
case '*': {
return 2;
}
case '/': {
return 2;
}
case '^': {
return 3;
}
case '~': {
return 4;
}
default: {
return 0;
}
}
}
public char associative(String symbol) {
switch (symbol.charAt(0)) {
case '+': {
return 'L';
}
case '-': {
return 'L';
}
case '*': {
return 'L';
}
case '/': {
return 'L';
}
case '^': {
return 'P';
}
case '~': {
return 'P';
}
default: {
return 0;
}
}
}
}
class InfixToPostfix {
private String sequence;
;
private int lenght;
private Stack stack;
private String output;
private boolean debug = false;
private Recognition rec;
public InfixToPostfix(String sequence) {
this.sequence = sequence;
this.lenght = sequence.length();
this.output = new String();
this.stack = new Stack(this.lenght);
this.rec = new Recognition();
}
public void convert() {
for (int i = 0; i < this.lenght; i++) {
String symbol = this.sequence.substring(i, i + 1);
if (debug) {
System.out.print(symbol);
}
if (rec.isLetter(symbol)) {
output += symbol;
} else if (rec.isOperator(symbol)) {
int symbolPrior = rec.getPriority(symbol);
/**
* Badanie łączności operatorów;
*/
// char associative = rec.associative(symbol);
//
// while (rec.isOperator(stack.peek())) {
// int topPrior = rec.getPriority(stack.peek());
// if (associative == 'P' && symbolPrior <= topPrior) {
// output += stack.pop();
// } else if (associative == 'L' && symbolPrior > topPrior) {
// output += stack.pop();
// } else {
// break;
// }
// }
//
// stack.push(symbol);
while (rec.isOperator(stack.peek())) {
int topPrior = rec.getPriority(stack.peek());
if (topPrior >= symbolPrior && !stack.isEmpty()) {
output += stack.pop();
if (stack.isEmpty()) {
break;
}
topPrior = rec.getPriority(stack.peek());
} else {
break;
}
}
stack.push(symbol);
} else if (rec.isOpenBracket(symbol)) {
stack.push(symbol);
} else if (rec.isCloseBracket(symbol)) {
while (!stack.peek().equals("(")) {
output += stack.pop();
}
stack.pop();
}
}
while (!stack.isEmpty()) {
output += stack.pop();
}
}
public String getResult() {
return (!this.output.isEmpty()) ? this.output : null;
}
}
class Stack {
private int top;
private String stack[];
public Stack(int stackSize) {
this.stack = new String[stackSize];
this.top = 0;
}
public boolean isEmpty() {
return (this.top == 0) ? true : false;
}
public String pop() {
if (isEmpty()) {
return null;
} else {
this.top -= 1;
return stack[top + 1];
}
}
public String peek() {
return (!isEmpty()) ? stack[top] : "";
}
public void push(String elem) {
++this.top;
this.stack[top] = elem;
}
}
class BinaryTree {
private Stack stack;
private Recognition rec;
private String sequence;
private int length;
public BinaryTree(String sequence) {
this.sequence = sequence;
this.rec = new Recognition();
this.length = sequence.length();
this.stack = new Stack(this.length);
}
public String convert() {
for (int i = 0; i < this.length; i++) {
String symbol = this.sequence.substring(i, i + 1);
if (rec.isLetter(symbol)) {
Node node = new Node(symbol);
this.stack.push(node);
} else if (rec.isOperator(symbol)) {
Node operator = new Node(symbol);
Node rhs = stack.pop();
Node lhs = stack.pop();
operator.right = rhs;
operator.left = lhs;
this.stack.push(operator);
}
}
Node top = stack.pop();
return visit(top, rec.getPriority(top.value));
}
public String visit(Node node, int prior) {
if (rec.isLetter(node.value)) {
return node.value;
}
String lhs = (node.left != null) ? visit(node.left, rec.getPriority(node.value)) : "";
String rhs = (node.right != null) ? visit(node.right, rec.getPriority(node.value)) : "";
if (!rec.isLetter(rhs) && rhs.charAt(0) != '(') {
rhs = "(" + rhs + ")";
}
String result =
lhs
+ node.value
+ rhs;
if (rec.getPriority(node.value) < prior) {
result = "(" + result + ")";
}
return result;
}
private class Node {
Node left;
Node right;
String value;
public Node(String value) {
this.value = value;
this.left = null;
this.right = null;
}
}
private class Stack {
private int top;
private Node stack[];
public Stack(int stackSize) {
this.stack = new Node[stackSize];
this.top = 0;
}
public boolean isEmpty() {
return (this.top == 0) ? true : false;
}
public Node pop() {
if (isEmpty()) {
return null;
} else {
this.top -= 1;
return stack[top + 1];
}
}
public Node peek() {
return (!isEmpty()) ? stack[top] : null;
}
public void push(Node elem) {
++this.top;
this.stack[top] = elem;
}
}
}