조건
1. 스택을 이용해서 구현한다.
2. 수식의 표기법(중위, 후위)을 이용한다.
구현상 어려웠던점
"수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다" 이부분이 구현이 상당히 까다로워서
들어오는 수식은 제대로 괄호 처리를 하였다는 제약조건을 두었다.(ㅠ.ㅠ)
h3.중위 표기법 과 후위 표기법
중위 표기법
후위 표기법
설명
중위 표기법을 후위 표기법으로 바꾸는 과정
A*B-C/D
1단계 : ((A*B)-(C/D))
2단계 : (AB)*-(CD)/)-
3단계 : AB*CD/-
컴퓨터 내부에서 수식을 처리하기에 가장 효율적인 코드는 후위 표기식이다.
후위 표기식은 괄호나 연산자 우선순위를 따로 처리 하지 않고 왼쪽에서 오른쪽으로 표기된 순서대로 처리 할수 있다.
//기존의 스택 코드 재활용
public interface Stack {
boolean isEmpty();
void push(String s);
String pop();
void delete();
}
public class LinkedListStack implements Stack {
private StackNode head = null;
private StackNode tail = null;
public int length = 0;
public void delete() {
pop();
}
public boolean isEmpty() {
// TODO Auto-generated method stub
return (this.length < 1);
}
public String pop() {
// TODO Auto-generated method stub
StackNode rntval = null;
if (isEmpty()){
//throw new NullPointerException("스택이 비었습니다.");
}else{
rntval= tail;
// 연결을 끊자.
StackNode temp = this.head;
for(int i=0; i < length -2; i++) {
temp = temp.link;
}
temp.link = null;
tail = temp;
length--;
}
return rntval.data;
}
public void push(String s) {
// TODO Auto-generated method stub
StackNode newStackNode = new StackNode(s);
if(isEmpty()){
this.head = newStackNode;
}else{
this.tail.link = newStackNode;
}
System.out.println(s + " : push() 되었습니다.");
this.tail = newStackNode;
++length;
}
}
검퓨터 내부에서 중위 표기법을 후위 표기법으로 바꾸는 과정
1단계 : 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽어 들인다.
2단계 : 피연산자를 만나면 출력한다.
3단계 : 연산자를 만나면 스택에 삽입 한다.
4단계 : 오른쪽 괄호를 만나면 스택을 pop 하여 출력한다.
5단계 : 수식이 끝나면 스택이 공백이 될 때까지 pop 하여 출력한다.
후위표기수식의연산방법
1단계 : 피연산자를 만나면 스택에 삽입한다.
2단계 : 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop 하여 연산하고, 연산 결과를 다시 스태에 삽입한다.
3단계 : 수식이 끝나면, 마지막으로 스택을 pop 하여 출력한다.
public class LinkedListStackCalc {
private String expresstion;
private int expresstionSize;
private char testChar; // 대상문자
private char openChar; // 현재문자 중괄호 또는 대괄호가 수식에 포함될때 사용
public boolean cheakExpresstion(String expresstion) {
this.expresstion = expresstion;
LinkedListStack lls = new LinkedListStack();
expresstionSize = expresstion.length();
for(int i=0; i< expresstionSize; i++){
this.testChar = expresstion.charAt(i);
switch (this.testChar) {
case '(' :
lls.push(String.valueOf(this.testChar)); break;
case ')' :
if(lls.isEmpty()) return false;
else{
this.openChar = lls.pop().charAt(0);
if((openChar == '(' && testChar != ')')) return false;
else break;
}
/*
case ')' :
case '}' :
case ']' :
if(lls.isEmpty()) return false;
else{
openChar = lls.pop();
if((openChar == '(' && testChar != ')') ||
(openChar == '{' && testChar != '}') ||
(openChar == '[' && testChar != ']'))
return false;
else break;
}
*/
}
}
if(lls.isEmpty()) return true;
else return false;
}
public String toPostFix(String inFIx){
char testChar;
String expresstion = inFIx;
int targetOperatorPostion = 0;
int expresstionSize = expresstion.length();
char postFix[] = new char[expresstionSize];
LinkedListStack lls = new LinkedListStack();
for(int i=0; i<expresstionSize; i++) {
try {
testChar = this.expresstion.charAt(i);
switch (testChar) {
case '0' :
case '1' :
case '2' :
case '3' :
case '4' :
case '5' :
case '6' :
case '7' :
case '8' :
case '9' :
postFix[targetOperatorPostion++] = testChar; break;
case '+' :
case '-' :
case '/' :
case '*' :
lls.push(String.valueOf(testChar)); break;
case ')' :
postFix[targetOperatorPostion++] = lls.pop().charAt(0); break;
default :
}
} catch (Exception e) {
// TODO: handle exception
}
}
postFix[targetOperatorPostion] = lls.pop().charAt(0);
return String.valueOf(postFix);
}
public int evalPostPix(String postFix) {
LinkedListStack lls = new LinkedListStack();
String expresstion = postFix.trim();
int operationFirst, operationSecond;
char testChar;
try {
for (int i = 0; i < expresstion.length(); i++) {
testChar = expresstion.charAt(i);
if ( testChar != '+' && testChar != '-'
&& testChar != '*' && testChar != '/') {
lls.push(String.valueOf(testChar));
}else{
operationSecond= Integer.parseInt(lls.pop());
operationFirst = Integer.parseInt(lls.pop());
switch (testChar) {
case '+': lls.push(String.valueOf((operationFirst + operationSecond))); break;
case '-': lls.push(String.valueOf((operationFirst - operationSecond))); break;
case '*': lls.push(String.valueOf((operationFirst * operationSecond))); break;
case '/': lls.push(String.valueOf((operationFirst / operationSecond))); break;
}
}
}
} catch (Exception e) {
// TODO: handle exception
}
return Integer.parseInt(lls.pop());
}
}
public class LinkedListStackCalcMain {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedListStackCalc llsc = new LinkedListStackCalc();
String exp1 = "(6*9)-(9/3)";
String exp2 = "(6*9)-(9/3))";
String exp3 = "6*9-9/3"; // 제대로 처리 안됨..
System.out.println("===================================");
System.out.println("표현식1 : " + exp1);
System.out.println("cheakExpresstion() : " + llsc.cheakExpresstion(exp1));
System.out.println("postFix : " + llsc.toPostFix(exp1));
System.out.println(llsc.evalPostPix(llsc.toPostFix(exp1)));
System.out.println("===================================");
System.out.println("표현식2 : " + exp2);
System.out.println("cheakExpresstion() : " + llsc.cheakExpresstion(exp2));
System.out.println("===================================");
System.out.println("표현식3 : " + exp3);
System.out.println("cheakExpresstion() : " + llsc.cheakExpresstion(exp3));
System.out.println("postFix : " + llsc.toPostFix(exp3));
}
}