후위연산식은 컴퓨터가 계산하기에 훨씬 편한 연산식 형태이다. 피연산자를 스택에 push하고 연산자를 만나면 스택에서 두개의 피연산자를 꺼내서 계산하고 다시 스택에 push한다. 스택이 공백이 될 때까지 진행하고 결과를 출력한다.
package stack_self;
class StackNode {
int data;
StackNode link;
}
class LinkedStack02 implements Stack02{
private StackNode top;
public boolean isEmpty() {
return (top == null);
}
public void push (int item) {
StackNode newNode = new StackNode();
newNode.data = item;
newNode.link = top;
top = newNode;
}
public int pop() {
if(isEmpty()) {
System.out.println("Deleting fail. Linked Stack is empty");
return 0;
}
else {
int item = top.data;
top = top.link;
return item;
}
}
private String exp;
public int evalPostfix(String postfix) {
LinkedStack02 LS = new LinkedStack02();
exp = postfix;
int opr1, opr2, value;
char testCh;
for(int i =0; i < postfix.length(); i++) {
testCh = exp.charAt(i);
if(testCh != '+' && testCh != '*' && testCh != '/' && testCh != '-') {
value = testCh - '0';
LS.push(value);
}
else {
opr2 = LS.pop();
opr1 = LS.pop();
switch(testCh) {
case '+' : LS.push(opr1 + opr2); break;
case '-' : LS.push(opr1 + opr2); break;
case '*' : LS.push(opr1 + opr2); break;
case '/' : LS.push(opr1 + opr2); break;
}
}
}
return LS.pop();
}
}
'Major > Data Structure & Algorithm' 카테고리의 다른 글
DFS(Depth First Search) (0) | 2022.06.01 |
---|---|
Binary Tree (0) | 2022.05.22 |
Stack , 괄호검사(Valid Braces), Infix to Postfix algorithm (0) | 2022.04.16 |
review (0) | 2022.04.16 |
원형 연결 리스트 (0) | 2022.04.16 |