자바 자료구조(중위 표기식에서 후위 표기식으로 변환)

[중위 표기식에서 후위 표기식으로 변환하는 알고리즘]

postfix(exp)

// exp는 주어진 중위 표기식으로 끝은 특수문자 ∞으로 가정

// PIS(스택 내 우선순위)와 PIE(수식 내 우선순위)는 우선순위를 반환해 주는 함수

// PIS (∞) ← -1, stack[0] ← ∞, top ← 0, stack[n]을 가정

while (true) do {

token ← getToken(exp);

case {

token = operand:

print(token);

token = ")" :

while (stack[top] ≠ "(") do

print(pop(stack));

top ← top - 1; // “(”를 제거. delete(stack)

token = operator : // “(”가 제일 높은 PIE를 가짐.

while (PIS(stack[top]) ≥ PIE(token)) do

print(pop(stack));

push(stack, token);

token = ∞ : // 중위식의 끝

while (top > -1) do

print(pop(stack))

print('∞');

return;

} // end case

} // end while

end postfix()

[위 알고리즘을 이용해 자바 코드를 작성하여야 하는데, 저는 밑의 코드와 같이 뒤죽박죽으로 일단 조금 짜놓았는데 다른 부분은 정말 어떻게 작성해야할 지 모르겠습니다ㅠㅜㅠㅠ]

public class Postfix {

public stack() {

stack_top = -1;

} // stack_top를 -1로 초기화한다.

char top() {

if(stack_top == -1) {

return -1; // stack_top이 -1이라면 배열은 비어있다는 의미로 예외 처리한다. 즉 -1을 반환한다.

}

private static int PIS(String temp) {

if (("^").equals(temp))

return 4;

if (("*").equals(temp) || ("/").equals(temp))

return 3;

if (("+").equals(temp) || ("-").equals(temp))

return 2;

if ((")").equals(temp))

return 1;

if (("(").equals(temp))

return 0;

return 0;

}

private static int PIE(String temp) {

if (("(").equals(temp))

return 5;

if (("^").equals(temp))

return 4;

if (("*").equals(temp) || ("/").equals(temp))

return 3;

if (("+").equals(temp) || ("-").equals(temp))

return 2;

if ((")").equals(temp))

return 1;

if (("=").equals(temp) || (" ").equals(temp))

return -1;

return 0;

}

case "+":

case "*":

case "-":

case "/":

case "(":

if (PIS(stringStack.top()) >= (PIE(token))) {

}

char getToken(char inexp[]) {

char token;

token = inexp[index];

index++;

return token;

}