티스토리 뷰
◆ Stack
|
top |
|
|
|
|
|
bottom |
stack 은 주로 배열을 이용하여 구현하며 , top에서 모든 입출력 즉 put 과 pop 등이 일어나는 구조이죠. put은 자료를 집어넣는 것이고 pop은 자료를 가져오고 그걸 지워주는 역할인 것 아시죠? 흔히들 스택을 가지고 후입선출(LIFO:Last Input First Output)방식이라고 하는데.. 나중에 들어온 값을 먼저 꺼낸다.? 뭔가 상식적으로는 맞지 않죠? 맞습니다. 하지만 특별한 경우에 이 방식을 이용하면 아주 쉽게 문제를 해결할수 있습니다. 그 예로는 공학계산기 인데.. 단순한 사칙연산 계산기가 아니라.
43^3-5+64*6+34 와 같이 사용자가 수식을 쭉 적은다음에
‘계산’이라는 버튼을 눌렀을 경우 프로그램이 알아서 연산자 우선순위를 따져서
계산을 하는 프로그램을 말합니다.
스택을 모른다면..정말 골치아픕니다. 어떻게 만드시겠어요? 노력에 비해 결과는 미흡할 것입니다. 어쨌든 공학계산기는 이번장(스택)의 맨마지막부분에 더 자세히 설명을 하겠으며 우선 스택의 원리와 간단한 소스를 봅시다.
처음에 얘기했듯이 스택은 top에서 모든 입출력이 일어나죠?
|
|
|
|
|
|
|
|
만약 위와 같이 저장장소를 4개 가지는 스택을 만들었다고 했을 때
이 스택에는 지금 아무것도 없습니다. 이를 가지고 top = -1 이라고 보통 씁니다. 그럼
여기에 “1 data" 라는 문자열을 넣었다고 가정했을 때
|
|
|
|
|
|
|
1 data |
이렇게 스택의 맨 아랫부분에 자료가 들어가며(put) top은 0이라는 값을 가지도록
해야합니다. 여기에 또 다시 정수 355을 넣었다면(put) 아래와 같이 되어야하죠
|
|
|
|
|
355 |
|
1 data |
top = 1
당연히 0.5323 이라는 실수(float)형을 넣더라도 똑같은 과정이 반복되겠죠?
|
|
|
0.5323 |
|
355 |
|
1 data |
top = 2
이렇게 말이죠..^^ 쉽죠?
top 에 들어가는 숫자는 프로그래머가 정해줘야 합니다. 그럼 왜 top라는 변수를
필요로 할까요?
만약 위의 스택에서 맨 나중에 들어온 값을 읽어들이고 스택에서 지우고자 한다면
즉 pop 시키길 원한다면 어떻게 해야 하죠?
top 이라는 변수를 쓰지 않았다면 가장 나중에 들어온 값이 어디에 있는지 알수가 없죠
만약 위와 같이 맨 나중에 들어온 값을 지운다면
|
|
|
|
|
355 |
|
1 data |
이렇게 되도록 만들어 줘야 합니다. 만약 여기서 hello 라는 문자열을 스택에 넣고자 한다면 top+1 해준다음 그 위치에 hello 라는 문자열 집어넣으면 되는것이죠.
따라서 top은 push,pop을 할 때 스택의 어느부분에서 해야하는지를 알려주는 일종의 포인터와 비슷한 역할을 합니다. 즉 위치를 알려주는 역할을 한다는 것이죠
그럼 아주 간단한 소스를 봅시다.
class Stack
{
Object Data[];
int top;
Stack (int init) {
Data = new Object[init];
top = -1;
}
Object pop() {
return Data[top--];
}
void push(Object element) {
Data[++top] = element;
}
}
public class Test {
public static void main(String[] args) {
Stack myStack = new Stack(5);
myStack.push("1 data");
myStack.push("2 data");
myStack.push("3 data");
myStack.push("4 data");
myStack.push("5 data");
for ( int i=1; i<=5; i++) {
System.out.println(myStack.pop());
}
}
}
이를 실행시키면
5 data
4 data
3 data
2 data
1 data
라고 나옵니다. 스택에 집어넣길 1 data , 2data 이렇게 오름차순으로 넣었는데
pop해서 보니까 5,4,3,2,1 data 로 나오죠? 즉 맨 나중에 넣은 5 data 가
가장 먼저 나온다는 것이죠. 여전히 왜 이런 방식을 알아야 할까? 궁금해 하실텐데
일단 이런것도 있구나 하세요. 조금후에 공학계산기에서 그 진가를 확실히 발휘하니까요
분석을 하면..
class Stack // 링크드 리스트와 마찬가지로 스택 클래스를 하나 만듭니다.
{
Object Data[]; // 보통 스택은 배열을 이용한다고 했죠?
int top; // top 이라는 변수는 push와 pop 할 때 위치
// 정보를 알려주기에 꼭 있어야 합니다.
Stack (int init) { // Stack 생성자 init 는 배열의 크기를 말합니다.
Data = new Object[init];
top = -1; // 스택에 아무것도 없는 것을 흔히 -1이라고 씁니다.
}
Object pop() { // 스택에 있는 값을 읽어오고 그것은 지웁니다.
return Data[top--]; // --top과 top-- 의 차이점 아시죠?
// 위의 문장은 다음과 같이 고쳐쓸수도 있어요
// 이해하기는 아래의 문장이 쉽겠네요..^^;
/* Object temp = Data[top]; temp 라는 변수에 top의 자료를 넣고
top = top - 1; top의 자료는 지웠으니 1만큼 값이 작아져야 하며
return temp; 읽어들인 자료를 반환해야 하니 top이 아니라
temp 리턴해야죠? top 은 이미 1만큼 작아졌으니.. */
}
void push(Object element) { // 스택에 값을 push 합니다.
Data[++top] = element; // element 값을 스택에
/* 넣는것이니 다음과 같이 바꿔쓸수도 있습니다. 여기서도 top++ 와 ++top의 차이점을 아셔야 합니다. top++은 top의 값을 그대로
사용한후 +1 시킨다는 것이며, ++top 은 top의 값을 +1 한후 그 값을 사용한다는 것이죠? 다 아실테니 길게 얘기 안합니다.
top = top + 1;
Data[top] = element; */
}
}
public class Test { // 여기가 중심이니 Test.java가 되는 것 알죠? 혹시나 싶어서..^^;
public static void main(String[] args) {
Stack myStack = new Stack(5);
// myStack 이라는 객체를 Stack 형으로 만들고 크기가 5인, 즉 5개의 값
// 을 저장할수 있는 스택을 만든다는 겁니다.
myStack.push("1 data"); // myStack에다가 데이터를 push합니다.
myStack.push("2 data"); // 어떤 식으로 push 되는지는 알필요가 없죠
myStack.push("3 data"); // Stack 클래스에서 다 처리를 했으니..
myStack.push("4 data");
myStack.push("5 data");
// 만약 myStack.push("6 data"); 라고 한다면 스택의 저장용량을
// 넘어섰으니 에러가 나서 컴파일이 안됩니다.
for ( int i=1; i<=5; i++) {
System.out.println(myStack.pop());
// 다섯 번 스택에 저장된 값을 pop 시킨후 프린트합니다.
}
}
}
Test 라는 클래스에는 push 와 pop 이라는 메소드를 사용했지만
top 이라는 변수는 전혀 사용하지 않았죠? 그 부분은 Stack 클래스에서
top-- , ++top 이런 것들 이용해서 top의 값을 조정한것이에요.
위의 소스에서 부족한 점이 있다면? 사용자가 스택의 저장용량을 넘어설만큼
자료를 많이 입력했을 때 대처방법이 없죠? 따라서
Stack 클래스에 inFull() 이라는 메소드를 첨가하고 push 할 때마다
스택이 가득차있는지 확인해야 겠죠? 가득차 있을 경우 “스택이 full입니다. 따라서
push 할수 없습니다.“ 라는 메시지가 나오도록 만들면 좀 더 섬세한 프로그램이 되는것이죠
그럼 스택이 가득찼는지 어떻게 알죠? top 이 배열의 전체크기와 같을때이죠?
Stack myStack = new Stack(5); 라고 했다면 배열의 크기를 5로 잡은 것이며
자료가 하나 들어갔을 때 top 은 0 이라는 값을 가지며
5개 모두 들어갔을 때 top 은 4라는 값을 가지죠? 아하~ top 과 배열의 length 와의
값을 비교하면 되겠구나~ 라고 아시겠죠? 자 !~ 그렇다면 그 반대로
스택에 아무런 값도 없는데 즉 top -1을 가질 때 또 pop 시킨다면 또한 에러가
나겠죠? 이때는 top 과 -1 이 같을 때 “스택에 아무값도 없어서 가져올게
없습니다.“ 라는 메시지를 출력하도록 한다면 좋겠죠?
아래의 소스는 위에 제시한 소스에서 이런 부분들을 개선한 코드입니다. 그럼 보시죠^^
고치거나 추가한 부분은 파란색으로 만들었습니다.
class Stack
{
Object Data[];
int top;
Stack (int init) {
Data = new Object[init];
top = -1;
}
Object pop() { // pop하기전에 isEmpty을 호출해서 pop 할수 있는
// 상황인지 알아봐야겠죠?
if ( isEmpty() == true) {
System.out.println("스택이 비워있어서 가져올게 없습니다.");
return null;
}
else
return Data[top--];
}
void push(Object element) {
// push 하기전에 isFull을 호출해서 push할수 있는 상황인지
// 알아봐야겠죠?
if ( isFull() == true) {
System.out.println("스택이 full입니다.");
}
else
Data[++top] = element;
}
boolean isFull() {
if ( top == Data.length-1) // 배열의 크기-1 한 것이 top 과 같을때
return true;
else
return false;
}
boolean isEmpty() {
if ( top == -1 ) // top 이 -1이라는 값을 가질때
return true;
else
return false;
}
}
public class Test {
public static void main(String[] args) {
Stack myStack = new Stack(5);
myStack.push("1 data");
myStack.push("2 data");
myStack.push("3 data");
myStack.push("4 data");
myStack.push("5 data");
myStack.push("6 data");
myStack.push("7 data");
for ( int i=1; i<=8; i++) {
System.out.println(myStack.pop());
}
}
}
만약 isFull 이나 isEmpty 라는 메소드를 만들지 않았다면 빨간색으로 된
부분들 때문에 컴파일 에러가 날겁니다. 하지만 잘못된 입력에 관한 처리를
하는 메소드를 만들었기에 출력창에 잘못된 입력이었다는 것을 알려주기만
하고 컴파일은 무리없이 됩니다.
출력은 이렇게 나옵니다.
스택이 full입니다.
스택이 full입니다.
5 data
4 data
3 data
2 data
1 data
스택이 비워있어서 가져올게 없습니다.
null
스택이 비워있어서 가져올게 없습니다.
null
스택이 비워있어서 가져올게 없습니다.
null
스택이 full입니다. <-- 이것이 두 번 나오죠?
스택의 저장공간은 5인데
myStack.push("6 data");
myStack.push("7 data");
라고 적어서 저장용량을 초과했죠? 그래서 push 메소드에서 이 부분처리를
한것이죠
for ( int i=1; i<=8; i++) {
System.out.println(myStack.pop());
}
이제 출력부분인데.. 지금 스택에는 1~5data 까지 들어가있습니다.
따라서 5번만 pop 할수 있는데 8이라고 적어서 8번 pop 하도록 해버렸죠?
따라서 처음5개의 값은 정상적으로 출력이 됩니다.
5 data
4 data
3 data
2 data
1 data
그리고 나서 가져올게 없는데 pop을 했으니 이 부분에 대한 처리메세지가
3번 나오게 되며 , null 이 나오는 이유는 return null; 이라고 했기에
null이 나오죠..
스택이 비워있어서 가져올게 없습니다.
null
스택이 비워있어서 가져올게 없습니다.
null
스택이 비워있어서 가져올게 없습니다.
null
별 것 아니죠?
혹 이런 물음을 가지는 사람도 있을겁니다. 저의 소스에는
항상 push를 먼저 다 한후 pop을 다 해버리는데 push 한후 pop하고
다시 push 도 가능한지요? 라고..말이죠
당연히 가능합니다. 똑같습니다. 다만 예제로 간단히 보이기 위해
저는 push 다 끝낸후 pop 해버리는 경우를 쓴것이죠
이제 어느정도 아실테니 다음의 예제를 보시죠. 그리고 그 결과를 예측해 보시기 바라며
(아~ 결과는 그래도 갈켜줄겁니다...^^;)
Stack class 부분은 모두 똑같으며 Test class 만 다음과 같이 다릅니다.
public class Test {
public static void main(String[] args) {
Stack myStack = new Stack(5);
myStack.push("1 data");
myStack.push("2 data");
System.out.println(myStack.pop());
myStack.push("3 data");
myStack.push("4 data");
System.out.println(myStack.pop());
System.out.println(myStack.pop());
myStack.push("5 data");
myStack.push("6 data");
System.out.println(myStack.pop());
myStack.push("7 data");
}
}
결과는
2 data
4 data
3 data
6 data
입니다.
1 data , 2 data를 push 했죠? 그럼 top은 1이 겠네요.
그 다음에 pop 했으니 top의 위치에 있는 데이터를 출력하는데
그게 바로 2 data 이죠? 그리고 가장 마지막에 입력한 값이 2 data 였으니 당연하죠?
다시 3 data , 4 data를 넣습니다. 그럼 지금 현재의 스택은
1 data , 3 data , 4 data 이런순으로 들어가 있겠으며 top은 2가 되겠네요
이번엔 pop이 두 번 나오죠? 그럼 4 data 가 먼저 출력되며, 그 러면 top 은 1 이 되며
pop이 두 번이었으니 top 1에 있는 3 data도 출력되겠죠? 그리고 나서
5 data, 6 data를 push 하고 그 후 pop 하니까 6 data 가 출력되겠죠?
따라서 2,4,3,6 이렇게 결과가 나오는 겁니다. 쉽죠?
자 이제는... 스택에 관한 기본이 쌓였을거라 생각되기에 공학계산기를
만들어 봅시다. 우선 postfix, infix, prefix부터...
infix : a+b <-- 흔히 사용하는 방식이죠. 사람이 판독하기에 편하죠
prefix : +ab <-- 연산자를 먼저(pre) 나오게 하는 방법.
postfix : ab+ <-- 연산자를 나중에(post)에 나오게 하는 방법
컴퓨터가 계산하기 쉬워하는 표현법은 prefix 혹은 postfix 랍니다.
왜 그러냐 하면은 . 우선 컴퓨터 구조에 관해 간략히 알려드리죠.
두 변수의 값을 더하기할 때, 여기선 a 와 b를 더하는 것이죠.
메모리에서 a 의 값을 읽어와서 CPU의 레지스터의 한부분 A에 넣고
다시 메모리에서 b 의 값을 읽어와서 CPU의 레지스터의 한 부분 B에 넣고 나서
A와 B에 들어있는 값을 더한후 레지스터의 한부분 C에 저장한후 이를 다시 메모리에
넣어줌으로써 두 값의 덧셈이 실행이 되는 겁니다. 즉 모든 계산은 메모리에서 일어나는 것이 아니라 레지스터에서 계산한걸 메모리로 넘겨줄 뿐이랍니다.
따라서 a+b 라고 하기보다는 ab+ 라고 한다면 바로 메모리에서 a와 b를 읽고 레지스터에 그걸 넣죠?. 그리고 나서 +를 보고서 아~ 이 두 값들을 덧셈하라는 것이구나~라고 CPU는 인식해서 덧셈을 하는것입니다. 이 부분에 관해선 자료구조의 범위를 뛰어 넘어
컴퓨터 구조에 관한 쪽이니 관심있으신 분은 책을 찾아보시기 바랍니다.
어쨌든 .. 사람이 인식하기 쉬운 infix(예 a+b) 보다는 postfix(예 ab+) 나 prefix(+ab)를 이용해서 복잡한 수식 계산의 그 기본 뼈대를 만들 수 있는 겁니다.
저는 공학계산기 만들 때 postfix 형태로 바꾼 후 계산을 할것이니 지금부터는
infix , postfix 형태를 좀 더 자세히 알아봅시다
a+b*c 는 분명히 infix 형태이죠?
자 그럼..이걸 다른 형태로 바꿔봅시다. postfix 형은 abc*+입니다. 하지만 a*b+c 의 postfix 형태는 ab*c+입니다. 뭔가 다르죠? 이렇게 다른 그 기준이 무엇일까요?
둘다 a,b,c 가 있고 +,*가 있는데 .. 이 연산자의 순서 때문에 postfix 형이 완전히 달라지는군요..
a+b*c 는 우선 b와 c 가 곱해줘야 하죠? 그리고 나서 a 와 덧셈을 하는것이고
a*b+c 는 순서대로 a 와 b를 곱한후 그리고 나서 c를 더하는 것이죠?
곱하기,나누기는 더하기 ,빼기 보다 우선순위가 높다는 것은 다들 아실겁니다. 바로 이러한 우선순위 때문에 postfix 형이 달라지게 됩니다.
postfix 형태를 해석하는 방법은
연산자(*,/,+,-) 바로앞의 두 변수를 연산자에 따라서 계산을 하는겁니다.
따라서 ab+ 는 + 앞에 a와 b라는 변수가 있으니 그것들을 더하는 것이죠
abc*+는 순서대로 읽었을 때 연산자 *가 +보다 먼저 나오죠?
그럼 *를 이용한 계산을 한후 +를 이용한 계산을 해야 하는겁니다.
*바로앞의 두 문자는 b와 c 이죠? 따라서 b와 c를 우선적으로 곱하기 한후
이값을 s 라고 임의로 정해봅시다.
abc*+에서 bc* 의 값은 s 라고 제가 정했기에
as+가 됩니다. 이제는 +에 관한 연산을 해야 하며
+앞에는 a 와 s 라는 변수가 있는 셈이죠? 따라서 a와 s를 더하면 끝납니다.
여기서 s 는 b와 c를 곱한결과가 들어있죠? 그리고 s 라는 변수는 제가
설명을 위해서 임의로 만든것일뿐입니다.
a*b+c 의 postfix 형태는 ab*c+ 였죠? 순서대로 봤을 때, *가 먼저나오는 군요
따라서 그 바로앞 두 변수 a 와 b를 곱해줍니다. 다음번 연산자로는 +가 있죠?
그 바로앞 두 개의 변수는 c 와 a,b를 곱한 결과이겠죠? 그것들을 더하면..끝
아직 왜 이런 방식을 알아야 하는지 의아해 할겁니다. 그리고 대강밖에 못 알아들을수도 있습니다. 하지만 곧 있으면 왜 이런 방식을 알아야 하며, 이런 postfix <-> infix 변환을
쉽게 할수 있을겁니다. 저또한 이것들 익숙해 지는데 약간 시간이 걸렸으며
알고 나면..정말 쉽고 재밌답니다. ^^;
조금 더 복잡한 postfix 형태를 해석해 봅시다.
abc**d+e- 라고 합시다. 곱하기가 연속으로 두 개 있는군요.. 아무것도 아니랍니다. ^^
우선 연산자는 *,*,+,-순으로 되어있죠? 순서에 맞게 처리해 주면 되니 특별할 것도 없답니다.
*바로앞에는 b와 c 가 있죠? 그러니 그 두 값을 곱한값이 bc*를 대체할 것이며
또 *가 있으니 그 바로앞 변수 a 와 bc*한 결과가 두 변수가 되겠죠? 그 값들을 또다시
곱해줍니다. 다음번 연산자는 +가 있죠? 그 바로앞 변수로는 두 번곱한 결과와 d입니다.
그 값들을 더하고 나서 e 와 그 결과를 빼면 끝납니다. 이젠 잘 알겠죠?
이를 infix 형태로 바꾸자면 b*c*a+d-e 혹은 a*(b*c)+d-e 라고 쓸수 있겠군요..
자~ 이번에는 그 반대로 infix 형태를 postfix 형태로 바꿔봅시다
a+b*c/d 는 b와 c를 곱하는 것이 우선이죠? 따라서 bc* 가 먼저나오게 되며
그 다음에는 b와 c를 곱한결과를 d 로 나누죠? 따라서
bc*d/가 되겠군요. 마지막으로 그 결과와 a를 더하죠? 그러므로 bc*d/a+입니다.
다음과 같이 읽으면 무리 없겠죠? b와 c를 곱한후 d로 나눈후 a를 더한다.
a+b-c/d 는? 우선 c를 d로 나누어야 하므로 cd/ 가 되며 +와 -는 우선순위가 똑같으니
왼쪽에서부터 먼저나오는 순서대로 처리하면 되죠? 따라서 + 먼저!
따라서 a와 b를 더하기 해야죠? 그러므로 cd/ 에다가 뒤에 ab+가 붙죠
그래서 cd/ab+ 이젠 -밖에 안 남았으니 ab+ 한 값에다가 cd/ 한 값을 빼면 되죠?
cd/ab+- 가 아니라 ab+cd/- 가 됩니다. 순서가 바뀌었죠? 아이구 ~ 이거 뭐야?
혼란스럽죠? 이런것들을 자료구조를 모른다면은 수많은 if 문들을 이용해서 처리해야하며 이 얼마나 비능률적이며 생각만해도 골치아프죠?
바로 이러하기에 stack을 이용해야 합니다. 자~ stack 이용하기전에 잠깐 시간을 내어서
각 연산자의 우선순위에 대해 알아 봅시다. *,/ 끼리는 똑같고 +,-끼리는 똑같죠?
그리고 * 은 +보다 앞서죠? 만약 프로그래머가 *,/의 우선순위를 13이라고 했고
+,-의 우선순위를 12라고 둔다면 ,즉 숫자 큰 것이 우선순위 높음을 뜻합니다. 일반적으로
1순위다~라고 말하면 그것이 가장 우선순위 높다는 뜻인데.. 여기선 그 반대를 뜻합니다.
꼭 이렇게 할 필요가 있을까?라고 물음을 둘수 있으나 저는 이렇게 배웠기에 그냥 이렇게 쓸랍니다. ^^; 나중에 스스로 바꿔보시던지..^^;;;
^ 은 거듭제곱을 뜻하며 a*b^c 는 b^c와 a를 곱하는 것이죠? 아하~ ^ 은 *,/보다 우선 순
위가 높구나~라고 알수 있으며 따라서 ^의 우선순위를 14라고 둡시다.
a*(b-c) 는 b와 c를 먼저 계산하죠? 무엇 때문에? 괄호때문이죠? 그리고 괄호가 나오면
무조건 그 안에것들부터 계산하죠? 따라서 괄호는 가장 우선순위가 높다는걸 알수 있으며
(을 20, )을 19로 둡시다. 왜 똑같이 하지 않나요?라고 물으신다면 나중에 보면 압니다.^^:
이렇게 각 연산자에 관한 우선순위들을 매겨놓았다고 가정하에 stack을 이용하여 postfix
형태로 바꿔봅시다.
a+b*c를 변환해 볼려고 합니다. 몇가지 원칙들이 있습니다
1. 스택을 두 개 만든다. 편의상 A stack, B stack 라고 합시다.
2. 변수는 무조건 A 스택(혹은 B 스택)에 push 한다. 즉 아무거나 잡아서 한곳에만 push!
3. 연산자는 변수가 들어가있는 스택 말고 다른 스택에 push 한다.
4. 만약 연산자가 스택에 push 될려고 할 때, top에 있는(바로 전에 push했던 연산자가
들어가있겠죠?) 연산자와 우선순위를 비교해서 들어가려는 연산자의 우선순위가 더 높을 때
만 push 되고 , 만약 같거나 이미 들어가 있는 연산자의 우선순위가 낮다면 pop 시켜서 이
값을 변수가 push 된 스택에 push 한다. 여기서 끝나는 것이 아니라 pop시켰으니 top은
1작아질것이며 그 곳에 있는 연산자와도 비교해서 들어갈려는 연산자의 우선순위가 더 높
지 않다면 또 pop시키고 그 값을 변수가 push 되어있는 스택에 push 해준다. 이런과정이
그 조건이 만족될때까지(들어갈려는 연산자의 우선순위가 더 클때까지) 반복된다.
빨간색 부분이 정말 중요합니다. 무슨 말인지 잘 모르겠죠?
예를 봅시다.~
a*b-c/d^e를 이와같은 규칙을 적용하면 postfix 형태로 바뀌게 될겁니다. 보시죠.^^
스택을 A,B 이렇게 두 개 만들었고 , A에는 변수가 , B에는 연산자가 우선 들어간다고
가정합시다.
infix 형태를 처음부터 쭉 읽어들이면서 규칙에 따라 적용하면 되요. 우선 a가 A에 들어가죠
|
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
지면(?)관계상 옆으로 스택을 그렸을뿐입니다. 헷갈리지 마세요
다음에는 *가 오는데 이건 Stack B에 넣는다는 가정하에서 지금하니까
B에 들어가죠. Stack B에는 지금 아무것도 없으니 뭐 연산자 우선순위 비교할것도 없죠?
따라서 A는 그대로 이고 B는 아래와 같이 됩니다.
|
* |
|
|
|
|
|
|
|
|
다음에는 b라는 변수가 오는군요. 당연히 Stack A 에 push 하면 되니 아래와 같죠?
|
a |
b |
|
|
|
|
|
|
|
이제는 -가 나오는 군요. Stack B에 넣을려고 하니까 * 라는 연산자가 존재하고 있죠? 따라서 연산자 우선순위를 고려해봐야 합니다. -는 아까전에 우선순위정할 때 12로 뒀죠? 그리고 *는 13으로 두었죠? 즉 방금 들어온 -라는 연산자의 우선순위가 이미 존재하는 즉 top에 있는 연산자 우선순위보다 작다는 거죠. 그러면 top에 있는 연산자를 pop시켜서 이를 Stack A(변수가 push 되는 스택)에 push 하는 것 맞죠? 그러면 Stack B 에는 아무것도 없게되니 더 이상 우선순위 따질 필요는 없고 - 연산자를 push 하면 되죠? 따라서 다음과 같이 됩니다.
|
a |
b |
* |
|
|
|
|
|
|
|
- |
|
|
|
|
|
|
|
|
그리고 나서 . c 가 있군요. A에 그냥 push 하니 다음과 같습니다.
|
a |
b |
* |
c |
|
|
|
|
|
그리고 나면 / 가 오는데 나누기는 우선순위 13이고 Stack B에 있는 -의 우선순위는 12이죠? 따라서 들어갈려는 연산자의 우선순위가 더 높기에 그냥 push 됩니다.
다음과 같겠네요
|
- |
/ |
|
|
|
|
|
|
|
그리고 d 가 오니까 A에 push 되어서
|
a |
b |
* |
c |
d |
|
|
|
|
처럼 되며
^ 이 오는군요
이것은 우선순위가 14라고 정했었죠? 일단 연산자이므로 Stack B에 들어갈려고 할것이며
top에 이미 연산자가 존재하고 있으니 우선순위 비교를 해야 합니다.
지금 top에는 / 이 있는데 이것은 우선순위 13이죠? 14가 더 크니 그냥 B에 push 될것이며 마지막 변수 e는 A에 push 되어서 다음과 같겠네요
|
a |
b |
* |
c |
d |
e |
|
|
|
|
- |
/ |
^ |
|
|
|
|
|
|
어랏 ! 모든 과정이 끝났는데 Stack B에 -/^이 남아있죠? 이걸 A에 옮겨야 정말로
postfix 형태가 완성되는 것이니... 프로그래머가 “만약 주어진 식이 끝나면 Stack B의 값을 차례대로 pop 시켜서 Stack A에 push 한다.” 라는 걸 수행하는 문장을 만들면 끝나겠네요.
그래서 완성된 postfix 형태는 Stack A에 있는 요소들을 bottom에서 top 까지 순서대로 읽으면 되겠네요. ab*cde^/- 이렇게 될것이며 맞는지 확인해 볼까요?
해석할땐 연산자바로 앞 두 변수를 가지고 생각하면 된다고 했죠?
여기선 *이 맨처음 연산자이니 우선 a와 b를 곱하겠군요. ab*에는그 결과값이 임시로 들어가있겠군요. 그리고 ^가 두 번째 연산자이네요. d와 e 가 그 바로앞 두 개의 변수가 되며
d^e 하라는 뜻이겠죠? 그 결과가 de^ 자리에 아마도 들어가 있겠구나~ 예상할수 있죠?
/가 세 번째 연산자이군요. 여기선 c 와 de^의 결과가 바로 앞 두 변수가 되죠? 즉 c를
de^한 값으로 나눈다~ 는 뜻이고 cde^/ 대신에 이 결과가 들어가겠네~ 예상하세여
마지막으로 -가 오는군요,. ab* 와 cde^/ , 이 두가지의 결과값들이 바로 앞 두 변수가 되겠군요. ab* 한 값에다가 cde^/ 한값을 빼주면 .. 결과가 나오겠네요
이를 infix 형태로 쓰면 {(a*b)-c/(d^e)} 이렇게 괄호를 써서 확실하게 쓸수도 있고
a*b-c/d^e 라고 써도 상식적으로 알고있는 우선순위를 생각하면 위의 괄호를 이용해서
만든 식과 똑같죠? .. 자~ 이렇게 Stack을 이용해서 위와 같은 규칙들을 적용하면
아무리 복잡한 식도 모두 다 postfix 형태로 바꿀수 있습니다.
여기서 한가지 의문점이 있을겁니다. postfix 형태가 컴퓨터로 계산하기 쉬운 형태라는 것은
알겠는데 프로그래밍을 어떻게 해야 하는가? 아직 postfix 형태로 바꾸는것만 했지 이를 가지고 우선순위에 맞게 계산하지는 않았잖아요.. 그렇죠? 이제 최종 목표인 이런 식들을 우선순위에 맞게 계산하여 그 결과를 얻는 부분을 알아봐야 겠죠?
일단 원칙을 알려드리죠
1. 최종 결과가 들어갈 스택을 하나 만든다. 이를 Stack F 라고 일단 임의로 정합시다.
2. postfix 형태를 bottom 에서부터 하나읽어들인다.
3. 읽어온 것이 변수이면 스택 F 에 push 한다.
4. 만약 읽어온 것이 연산자이면 스택 F 에 있는 것을 두 번 pop 한다.
5. 처음에 pop 한 값을 Object A 에 집어 넣고
6. 두 번째로 pop 한값을 Object B 에 집어 넣는다.
7. A 와 B 값을 연산자에 맞게 계산한후 이를 스택 F 에 push 한다.
이렇게 보니까 뭐가 이케 많어? 라고 생각할수도 있는데 알고 보면 아무것도 아닙니다
그리고 Stack F, Object A,B 이렇게 쓰는데 그냥 임의로 정한것이니 Stack DDD 라고 써도 되는 것 아시죠?
가장 쉬운 예인 ab-를 가지고 최종 결과를 알아봅시다.
1. Stack F를 만들고
2. bottom에서부터 하나씩 읽어들인다.
3. 맨 먼저 a를 읽어오며, 이는 변수 이므로 F에 push 한다. 또 읽으면 b 이고,. 이 또한 변수이므로 F에 push 한다. 따라서 현재상태의 Stack F는 다음과 같다.
|
a |
b |
|
|
|
a 가 bottom 의 위치에 있고 b 가 top의 위치에 있다.
4. 또 읽어들이면 -가 오며, 이는 연산자이기에 F를 두 번 pop한다.
5. 처음 pop 시키면 b가 나오게 되며 이를 Object A = b; 처럼 해서 대입한다
6. 두 번째 pop하면 a 가 나오게 되며 이를 Object B = a; 처럼 해서 대입한다.
7. B-A 한 값을 스택 F에 push 한다. 만약 곱하기였다면 B*A의 결과를 push한다.
이렇게 하면 , 스택 F 에는 A-B 한 값밖에 없게 되죠.
프로그래머는 이런 과정이 모두 끝난후 스택 F를 한번 pop시켜서 그 값을 화면에
표시해 주기만 하면 됩니다. 대강 아시겠죠? 확실히 알 필요없습니다. 그냥 어떻게
돌아간다 정도만... 실제로 여러번 다른 예를 보시면 더 쉽게 알게될겁니다.
이번에는 아까전에 만든 postfix 형태를 가지고 계산을 한번 해 봅시다. ab*cde^/-
이것은 연산자가 4개나 있고 변수는 5개나 있군요.. 쫄지맙시다.
위와 같이 하면 다 똑같이 됩니다.
1. 우선 스택 F를 하나 만듭니다.
2. bottom에서부터 하나씩 읽어들이는데 변수이면 F에 push 하고 연산자이면
F를 두 번 pop해서 연산자에 맞게 계산한후 push 하라고 했죠?
3. 첫 번째 읽어온 것은 a 일 것이며, 변수니까 push 하고 그 다음번 읽어온 것도 변수니까 b를 push 합니다. 현재 스택은 다음과 같겠네요
|
a |
b |
|
|
|
4. a b 다음에는 *가 있으니 연산자이며 따라서 Stack F를 두 번 pop 해야 겠네요
처음 pop 한 값을 OBject A 에 넣습니다. A에는 당연히 b 가 들어가는군요
그 다음 pop 한 값을 Object B 에 넣습니다. B 에는 a 가 들어가는군요
그리고 연산자가 * 였으니 B*A한 결과가 스택 F에 push 합니다. 따라서
이렇게 하면 스택 F는 다음과 같겠군요. a b 는 다 없어졌죠? 아까 전에 두 번 pop
해버렸으니..당연히..그리고 B*A 한 값을 push한다고 했으니 .. 이해 가죠? --+
|
B*A 혹은 a*b |
|
|
|
|
5. ab*cde^/- <-- postfix 형태가 이것이었으니..
이번에는 cde 가 계속 있으니 이것들은 모두 변수 이므로 push 되어서
다음과 같이 됩니다.
|
B*A 혹은 a*b |
c |
d |
e |
|
6. 위와 같이 하고 나면 이젠 ^을 읽어들일것이며 , 이것은 연산자이니 F를 두 번 pop 해서 그 값을 Object A'와 B'에 넣습니다. 이경우엔
A' 에는 e 가 들어가며, B' 에는 d가 들어가는군요
연산자가 ^이니 거듭제곱이라는 뜻이죠? 따라서 B‘^A' 한 값을 push 합니다.
F는 다음과 같겠군요.
|
B*A 혹은 a*b |
c |
B'^A' 혹은 d^e |
|
|
7. 다음번 읽어들이는 값은 / 이군요. 아이구 이것도 연산자이네.. 또다시 두 번 pop합니다.
B'^A'(혹은 d^e) 와 c를 가지고 나누기 연산한후 push 하니까. 이젠 예상 할수있죠?
다음과 같습니다.
|
B*A 혹은 a*b |
c/(d^e) |
|
|
|
8. 마지막으로 -가 나오는군요. 얼라리요. 이것도 연산자네.. 두 번 pop하고 -연산을 한후
그 결과를 push합니다. 다음과 같겠네여~
|
(a*b)-{c/(d^e)} |
|
|
|
|
이제 모든 과정이 끝났으니 스택 F를 pop해서 그 값을 출력하면 끝나는군요
아니 이보세요! 이런 원칙하에 계산을 하면 postfix 형태를 가지고 우선순위에 맞게
계산을 할수 있는 것은 알겠는데요. 누가 이렇게 금방 알수 있나요? 이런 원칙을 만들게된
원리 같은 것은 왜 안 갈켜줘요? 라고 물으실수 있는데
그것은 저도 모릅니다. 어떤 머리좋으신 분이 연구해서 알아냈겠죠..알고리즘 연구 같은걸로. 아마도 알고리즘 같은 수업을 들어야 저도 왜 이렇게 해야 하는지 알수있을 것 같구요
다만 이런 방식으로 하면 우선순위에 맞게 계산이 된다는것이며
초보 프로그래머는 이 방식대로 따라하면 됩니다. 나중에 이런 방식이 싫다면
새로운 방식을 개발해 내시던지..^^;
공학 계산기에 관한 원리,원칙만 지금까지 얘기를 했기에 그 구체적인 소스는
어떻게 구현을 할까? 궁금해 하실 겁니다. 조금만 있다가 다루죠. 지금까지 한것들을
정리 하면 .. 공학계산기를 만들때는
가장 중요한 것이 사용자가 식을 쭉 적어두고 나서 그걸 계산하는 것이므로
연산자 우선 순위에 맞게 계산을 해야합니다. 이를 위해선
프로그래머가 각 연산자에 관한 우선순위를 미리 정해두고나서
어떤 연산자를 읽어들었을 때 , 그것에 맞는 우선순위를 가지고, 먼저 계산을 하느냐
혹은 나중에 계산을 하느냐가 결정이 되는 겁니다.
우선 사용자가 만든 infix 형태를 postfix 형태로 바꾸어야 하며 , 이 과정에서
각 연산자 우선순위에 맞게 스택에 pop와 push 가 이루어졌죠?
이렇게 해서 postfix 형태를 하나 만든후 이걸 가지고 진짜로 원하는 계산결과를
출력해야 하기에 , 읽어들인 값이 변수인가 아니면 연산자인가에 따라서
pop과 push를 했으며 , 최종적으로 하나의 스택에 최종 결과만 남게 되니
그걸 pop 해서 화면에 출력하는 거였습니다. 앞엣것들 제대로 안 봤다면 지금 이렇게
정리하는 말도 못 알아 들을껄요~ ^^
자 이제부터 하나씩 하나씩 공학계산기를 자바로 만들어봅시다.
우선 스택 클래스는 다음과 같이 만들면 되겠죠?
배열을 이용한 스택 이므로 이름을 StackArray 라고 저는 정했습니다.
class StackArray{
Object firstStack[];
int top;
StackArray(int size){ // 생성자
firstStack = new Object[size];
top = -1; // empty로 초기화
}
Object getItem(int index) { // index번째의 원소 리턴
return firstStack[index];
}
void push(Object ele) { // top에 원소 집어넣기
firstStack[++top] = ele;
}
Object peek() { // top의 원소 보기..
return firstStack[top];
}
Object pop() { // top의 원소 빼오기.
return firstStack[top--];
}
}
++top과 top--는 저번에 설명했었죠? 다시 한번 얘기하자면 push 할 때는
top을 하나 증가시킨후 그 위치에 값을 넣는것이죠? 그래서
firstStack[++top] = ele; 는
top = top +1;
firstStack[top] = ele; 와 똑다고 했죠?
return firstStack[top--]; 는
temp = firstStack[top];
top = top -1;
return temp; 와 똑같다고 했죠? 다 잘 아시죠?
뭐 특별히 어려울 것은 없다고 봅니다.
그리고 자료구조라기 보다는 이를 실현하기 위해 자바에 관해 약간 알아봅시다.
저번에 링크드리스트할 때 사용한 StringTokenizer 라는 겁니다. 다시 복습을 하자면
지금 해야할 우선 과제는 a+b*c를 postfix 형태로 바꿔야 하는것이죠?
사용자가 다음과 같이 입력을 했을 경우 , a ,+, b, *, c 로 모두 구분시켜야 합니다.따라서 StringTokenizer를 써야 하며 그 구분자로는 모든 연산자를 두면 되겠네요. infix 형태는 변수와 변수사이에 연산자가 있으니까요. 즉
String nToken; // nextToken 즉, 하나하나의 토큰을 넣기위한 문자열.
StringTokenizer parser;
parser = new StringTokenizer(inputData,"+-*/^%",true);
inputData는 사용자가
입력한 infix 형태가 저장된 문자열을 뜻함. true을 해야 연산자를 알수 있기에 반드시
true 해야함. StringTokenizer 에 관해선 이미 앞에서 많이 다루었기에 아직도
기억이 가물가물 하시면 링크드리스트를 이용한 다항식계산기 부분을 다시 보세여.
아래의 소스는 a+b*c 라는 infix 형태를 postfix 형태로 바꾸는 가장 간단한 프로그램입니다. 3개의 클래스가 있으며
StackArray 라는 스택를 나타내는 클래스. Priority 라는 연산자 우선순위를 알려주는 클래스
그리고 Test 라는 main 클래스입니다. 참고로 Stack 이라는 클래스는 보통 자바 컴파일러가 기본적으로 제공하는 클래스명일 가능성이 높기에 저는 ArrayStack 라고 이름을 지었으며 실제로 여러 자료구조에 관한 클래스들이 기본적으로 제공되지만,, 지금 이렇게 그것들에 관해 처음부터 살펴보는 까닭은 그 원리를 제대로 알아야 응용과 더 나은 개발이 가능하며 남이 만든 것 붙여쓰기만 하면 언젠가는 근본 약한 것이 드러나게 되기 때문입니다.
// Test.java
import java.lang.String;
import java.util.StringTokenizer;
class StackArray{ // 스택 클래스
Object firstStack[];
int top;
StackArray(int size){ // 생성자
firstStack = new Object[size];
top = -1; // empty로 초기화
}
Object getItem(int index) { // index번째의 원소 리턴
return firstStack[index];
}
void push(Object ele) { // top에 원소 집어넣기
firstStack[++top] = ele;
}
Object peek() { // top의 원소 보기..
return firstStack[top];
}
Object pop() { // top의 원소 빼오기.
return firstStack[top--];
}
}
class Priority { // 우선순위 알려주는 클래스
int getPri(Object ob) { // 우선순위를 리턴해 주는 메소드
String operator = (String)ob;
int pri = -1;
if ( operator.equals("+") )
pri = 12;
if ( operator.equals("-") )
pri = 12;
if ( operator.equals("*") )
pri = 13;
if ( operator.equals("/") )
pri = 13;
if ( operator.equals("%") )
pri = 13;
if ( operator.equals("^") )
pri = 14;
return pri;
}
}
public class Test {
public static void main(String args[]) {
String inputData = "a+b*c"; // 입력한 infix형태의 수식을 inputData에 넣음..
String nToken; // 토큰을 하나씩 받아와서 저장할려고..
StringTokenizer parser;
parser = new StringTokenizer(inputData,"+-*/^%",true);
int num = parser.countTokens(); // 각 원소 갯수를 알아냄. a,+,b,*,c 여기선 5가 됨.
StackArray mainStack = new StackArray(num); // 실제로 필요한 스택자료저장
StackArray tempStack = new StackArray(num); // +-/ 등(연산자)을 임시 저장하기위해
// 스택 사이즈로 num을 쓴 이유는 스택에는 각 원소(변수와 연산자)가 들어가므로
// 최대 사이즈가 그 원소의 총 개수와 같거나 작을뿐이기에 여유있게 잡아줌....
String operators = "+-*/^%"; // nToken의 값이 연산자인지 구별위해...
while (parser.hasMoreTokens()) { // 토큰이 없을때까지 실행
nToken = parser.nextToken();
boolean isOperator = false;
// 연산자인지 아닌지 판별. 기본적으로 false. 즉 연산자 아님을 뜻함.
for ( int i=0 ; i < operators.length() ; i++ ) {
if ( nToken.equals(operators.substring(i,i+1)) ) // 만약 nToken이 연산자이면 true!
isOperator = true; // 연산자일경우만 isOperator에 true를 넣어줌.
}
if ( isOperator == true ) { // 연산자일경우 , 연산자 우선순위에 따라 처리..
Priority p = new Priority(); // 우선순위 관련 클래스를 만든다.
while ( (tempStack.top >= 0 && p.getPri(nToken) <= p.getPri(tempStack.peek())) ) {
// nToken의 우선순위와 스택 top에 있는 연산자의 우선순위를 비교하여
// 스택 top의 것이 같거나 클때, 반복수행됨.
// 연산자가 저장된 스택(tempStack)의 top의 것을 pop하여
// 다른 스택에 아래와 같이 push한다.중요!
mainStack.push(tempStack.pop()); // 변수가 저장되는 스택에 pop한것을 push한다.
}
tempStack.push(nToken); // nToken의 우선순위가 스택 top에 있는 연산자 우선순위보다
//큰것을 만족할때 nToken(연산자가 들어가있음)을 연산자가 들어가는 스택에 push한다.
}
if ( isOperator == false) // 일반 숫자일 경우는 그냥 push한다.
mainStack.push(nToken);
}
while ( tempStack.top >= 0 ) {
// 일단 모든 parser에 관해 처리를 했다면 남아있는 것(tempStack)들을 모두 pop해서 mainStack에 push한다.
mainStack.push(tempStack.pop());
}
String userView="";
for (int i=0; i<=mainStack.top ;i++ ) {
userView = userView + mainStack.getItem(i);
// 화면에는 pop을 이용해서 보이게 할수 없으므로..처음부터 get..
}
System.out.println(userView);
}
}
가장 기본적인 소스입니다. 이 부분을 하나라도 제대로 이해하지 못한다면 앞으로 힘들것이니 꼭 곰곰이 따져보고 살펴보시길...바랍니다.
결과에는 abc*+ 라고 나옵니다.
만약 String inputData = "a+b*c"; 대신에 String inputData = "a-b/c^d+e"; 라고 했다면
결과는 abcd^/-e+ 라고 나올겁니다. 확인해 봤습니다. ^^
이제 위의 소스를 완벽히 이해하셨다면 공학계산기 만드는 것 50%는 거의 다 한것입니다.
아직 절반이 남아있죠? 지금까진 infix 형태를 postfix 형태로 바꾸기만 했으니 이젠
이를 가지고 직접 계산하는 소스를 만들어 봅시다.
우선 아래를 보시죠
1. 최종 결과가 들어갈 스택을 하나 만든다. 이를 Stack F 라고 일단 임의로 정합시다.
2. postfix 형태를 bottom 에서부터 하나읽어들인다.
3. 읽어온 것이 변수이면 스택 F 에 push 한다.
4. 만약 읽어온 것이 연산자이면 스택 F 에 있는 것을 두 번 pop 한다.
5. 처음에 pop 한 값을 Object A 에 집어 넣고
6. 두 번째로 pop 한값을 Object B 에 집어 넣는다.
7. A 와 B 값을 연산자에 맞게 계산한후 이를 스택 F 에 push 한다.
위의 것은 앞서 얘기한 postfix 형태를 가지고 최종 결과얻는 원칙을 붙여넣기 한겁니다.
까먹은 분들중에 귀찮아서 다시 앞장 뒤져서 복습 안하시는 분들이 있을 것 같아서
이케 다시 쓴겁니다. ^^v
별 것 없죠? 임의의 스택을 만든후에 이미 만들어 놓은 postfix 스택의 bottom에서부터
하나씩 읽어와서 변수이면 방금 만든 임의의 스택에 push 하고 연산자이면
두 번 pop해서 연산자에 맞게 계산을 한후 임의의 스택에 push 한다. 쉽죠?
그럼 소스를 보시죠. 이번에는 아까전에 만든 소스에서 main 메소드에
makePostFix(); 와 makeFinal(); 이라는 메소드를 호출하도록 했습니다.
makePostFix 는 단어에서 알수있듯이 postfix 형태 만드는 메소드이며 , 이것은 이미 만들었었죠? 그리고 makeFinal 은 이 postfix 형태를 가지고 최종 결과를 얻는 메소드랍니다.
그럼 진짜로 보셔여~ 아참. 이번예제에선 infix 형태가 a*b 같은게 아니라
실제 수 , 즉 3*5^43 같은걸로 잡았습니다. 이렇게 해야 실제 계산이 가능하겠죠?
import java.lang.String;
import java.util.StringTokenizer;
class StackArray{ // 스택 클래스
Object firstStack[];
int top;
StackArray(int size) { // 생성자
firstStack = new Object[size];
top = -1; // empty로 초기화
}
Object getItem(int index) { // index번째의 원소 리턴
return firstStack[index];
}
void push(Object ele) { // top에 원소 집어넣기
firstStack[++top] = ele;
}
Object peek() { // top의 원소 보기..
return firstStack[top];
}
Object pop() { // top의 원소 빼오기.
return firstStack[top--];
}
}
class Priority { // 우선순위 알려주는 클래스
int getPri(Object ob) { // 우선순위를 리턴해 주는 메소드
String operator = (String)ob;
int pri = -1;
if ( operator.equals("+") )
pri = 12;
if ( operator.equals("-") )
pri = 12;
if ( operator.equals("*") )
pri = 13;
if ( operator.equals("/") )
pri = 13;
if ( operator.equals("%") )
pri = 13;
if ( operator.equals("^") )
pri = 14;
return pri;
}
}
public class Test {
static StackArray mainStack; //postfix 형태로 변형시킨 식이 들어가 있음.
static StackArray rStack; // 최종결과가 들어있는 스택
public static void main(String args[]) {
makePostFix(); // postfix형태로 만드는 메소드 호출.
makeFinal();
System.out.println("최종결과" + rStack.pop());
}
static void makePostFix() {
String inputData = "12+34*5"; // 입력한 infix형태의 수식을 inputData에 넣음..
String nToken; // 토큰을 하나씩 받아와서 저장할려고..
StringTokenizer parser;
parser = new StringTokenizer(inputData,"+-*/^%",true);
int num = parser.countTokens(); // 각 원소 갯수를 알아냄. a,+,b,*,c 여기선 5가 됨.
mainStack = new StackArray(num); // 실제로 필요한 스택자료저장
StackArray tempStack = new StackArray(num); // +-/ 등(연산자)을 임시 저장하기위해
// 스택 사이즈로 num을 쓴 이유는 스택에는 각 원소(변수와 연산자)가 들어가므로
// 최대 사이즈가 그 원소의 총 개수와 같거나 작을뿐이기에 여유있게 잡아줌....
String operators = "+-*/^%"; // nToken의 값이 연산자인지 구별위해...
while (parser.hasMoreTokens()) { // 토큰이 없을때까지 실행
nToken = parser.nextToken();
boolean isOperator = false;
// 연산자인지 아닌지 판별. 기본적으로 false. 즉 연산자 아님을 뜻함.
for ( int i=0 ; i < operators.length() ; i++ ) {
if ( nToken.equals(operators.substring(i,i+1)) ) // 만약 nToken이 연산자이면 true!
isOperator = true; // 연산자일경우만 isOperator에 true를 넣어줌.
}
if ( isOperator == true ) { // 연산자일경우 , 연산자 우선순위에 따라 처리..
Priority p = new Priority(); // 우선순위 관련 클래스를 만든다.
while ( (tempStack.top >= 0 && p.getPri(nToken) <= p.getPri(tempStack.peek())) ) {
// nToken의 우선순위와 스택 top에 있는 연산자의 우선순위를 비교하여
// 스택 top의 것이 같거나 클때, 반복수행됨.
// 연산자가 저장된 스택(tempStack)의 top의 것을 pop하여
// 다른 스택에 아래와 같이 push한다.중요!
mainStack.push(tempStack.pop()); // 변수가 저장되는 스택에 pop한것을 push한다.
}
tempStack.push(nToken); // nToken의 우선순위가 스택 top에 있는 연산자 우선순위보다
//큰것을 만족할때 nToken(연산자가 들어가있음)을 연산자가 들어가는 스택에 push한다.
}
if ( isOperator == false) // 일반 숫자일 경우는 그냥 push한다.
mainStack.push(nToken);
}
while ( tempStack.top >= 0 ) {
// 일단 모든 parser에 관해 처리를 했다면 남아있는 것(tempStack)들을 모두 pop해서 mainStack에 push한다.
mainStack.push(tempStack.pop());
}
String userView="";
for (int i=0; i<=mainStack.top ;i++ ) {
userView = userView + mainStack.getItem(i);
// 화면에는 pop을 이용해서 보이게 할수 없으므로..처음부터 get..
}
System.out.println("postfix형태로 바꾼것:" + userView);
}
static void makeFinal() {
rStack = new StackArray(mainStack.top+1);
// 만약 3개가 들어있으면 top은 2라는 값을 가지므로 +1 해 줘야
// 안전하게 스택사이즈 결정할수 있다.
for ( int i=0; i <= mainStack.top ; i++ ) {
Object t = mainStack.getItem(i); //i 번째 원소를 리턴해서 t에 대입.
if ( t.equals("+")||t.equals("-")||t.equals("*")||t.equals("/")||t.equals("%")||t.equals("^")) {
// 연산자일경우. 아래와 같이 두번 팝(pop)한다.
double latter = Double.valueOf((String)rStack.pop()).doubleValue();
//pop는 뒤에서부터 가져오는것이므로 먼저가져온것이 실제로 후자.
double former = Double.valueOf((String)rStack.pop()).doubleValue();
double temp = -1; // 계산결과를 저장하는 변수,일단 임의의 값 -1대입.
if ( t.equals("+") )
temp = former+latter;
if ( t.equals("-") )
temp = former-latter;
if ( t.equals("*") )
temp = former*latter;
if ( t.equals("/") )
temp = former/latter;
if ( t.equals("%") )
temp = former%latter;
if ( t.equals("^") )
temp = getSquare(former,latter);
rStack.push(temp+""); // 계산결과(temp)를 push해 준다.
}
else { // 연산자가 아닐경우
rStack.push(t); // 그냥 push해줌.
}
}
}
static double getSquare(double x,double exp) { // 거듭제곱은 지원하지 않기에 만들어야함.찾아보면 있을수도 // 있고..^^
int i;
double temp=1;
for (i=1 ; i<=exp ; i++ ) {
temp = temp * x;
}
return temp;
}
}
여기까지는 기본적으로 모두 이해가 가야 합니다. 그냥 눈으로 슬쩍 본다고 되는 것이 아니니 실제로 코드도 스스로 만들어 보고 .. 어느정도 시간투자가 필요할 겁니다.
이까지 따라오셨다면 이젠 공학계산기 80%는 완성인겁니다. 이제 남은 것은 괄호 처리와 애플릿등으로 GUI 구현하는 겁니다. GUI는 어렵지 않기에 스스로 해 보시면 될것이며
괄호처리에 관해 알아봅시다. 사칙연산 하면서 함께 언급하지 않은 이유는 당연히 복잡하니까 나중에 따로 이렇게 다루기 위한겁니다.
5*(6+7)를 한번 postfix 형태로 바꿔볼까요? 우선 예전에 제가 쓴 infix 형태를 postfix 형태로 바꾸는 원칙을 다시 봅시다.
1. 스택을 두 개 만든다. 편의상 A stack, B stack 라고 합시다.
2. 변수는 무조건 A 스택(혹은 B 스택)에 push 한다. 즉 아무거나 잡아서 한곳에만 push!
3. 연산자는 변수가 들어가있는 스택 말고 다른 스택에 push 한다.
4. 만약 연산자가 스택에 push 될려고 할 때, top에 있는(바로 전에 push했던 연산자가
들어가있겠죠?) 연산자와 우선순위를 비교해서 들어가려는 연산자의 우선순위가 더 높을 때
만 push 되고 , 만약 같거나 이미 들어가 있는 연산자의 우선순위가 낮다면 pop 시켜서 이
값을 변수가 push 된 스택에 push 한다. 여기서 끝나는 것이 아니라 pop시켰으니 top은
1작아질것이며 그 곳에 있는 연산자와도 비교해서 들어갈려는 연산자의 우선순위가 더 높
지 않다면 또 pop시키고 그 값을 변수가 push 되어있는 스택에 push 해준다. 이런과정이
그 조건이 만족될때까지(들어갈려는 연산자의 우선순위가 더 클때까지) 반복된다.
이를 참고하여 5*(6+7)를 postfix 형태롤 바꿔봅시다. 결과는 아마도
567+*가 되어야 겠군요. 따라서 두 개의 스택을 만들고 push , pop 한 결과 한쪽에는 567이 들어가 있고 나머지 한쪽에는 *+가 들어가있어야 겠네요. 그래야 마지막으로 연산자가 들어가 있는 스택을 차례대로 pop해서 변수가 들어있는 스택에 push 하니까. 567+* 형태가 되겠죠? 자,그럼 편의상 스택 A,B 라 두고 A에는 변수가 B에는 연산자가 들어가게 합시다. 그리고 괄호처리에 관한 원칙들을 보시죠. 밑에 있어여
1. ‘(’는 icp(incoming procedence) 일 경우 우선순위는 20, isp(in-stack procedence) 일 경우는 우선순위 0 이라고 둔다.
2. ‘)’는 우선순위 19로 둔다.
3. 스택안에 ‘(’이 있을 경우 ‘)’이 들어올때까지 무조건 기다림.즉 연산자가 들어가는 스택에 ‘)’이 push 될려고 할 때, push 되는게 아니라 ‘(’이 나올때까지 계속 pop해서 변수가 들어있는 스택에 push 한다. -중요
4. icp 란 infix 형태에서 읽은 값이 ‘(’일 경우이고, isp 는 스택안에 넣어둔 값이 ‘(’일 경우. 즉 어차피 같은 ‘(’인데 스택에 들어갈려는 경우과 이미 들어가 있을 경우의 우선순위가 달라진다는 뜻이죠. -중요
문 소린지 모를겁니다. 저도 처음에 그랬으며 , 지금 복습중인데도 헷갈리네요. ^^;;
5*(6+7)을 이와같은 원칙에 의해 한번 해 볼까요?
스택 A,B를 만든다. 5가 맨 먼저 나오니 A에 push한다.
*가 나오니 B에 push 한다. ‘(’가 나오는데 지금 스택에 들어갈려는 중이니까 icp 이다. 따라서 연산자 우선순위는 20이니 B에 그냥 push 된다. 6이 온다. A에 push 되겠군.
+가 온다. 우선순위 12이며 , 현재 B의 top에 있는 연산자는 ‘(’이며 스택안에 있으므로
isp 이다. 따라서 우선순위는 0이며, +가 더 크므로 +는 그냥 push된다.
현재 A,B안의 모습은 다음과 같겠네요
Stack A: 5 6
Stack B: * ( +
이제 7이 오니 A에 push 되고, ‘)’가 오네요. ‘)’는 push 되는게 아니라 ‘(’이 나올 때 까지 B를 pop해서 그 원소들을 A에 push 한다고 했죠? 따라서 +가 pop되어 A에 push 되는군요. 그리고 ‘(’와 ‘)’는 실제 계산 연산을 하는 역할을 하지 않기에 없애면 됩니다.
따라서 현재 A,B의 상태는 다음과 같겠군요
Stack A: 5 6 7 +
Stack B: *
이젠 모두 끝났으니 B의 원소들을 차례대로 pop해서 A에 push 하면 되죠?
최종 결과는 5 6 7 + * 이군요
다른 예를 보죠
(2+3*4)^1/(6*7)을 위와 같은 규칙에 따라 postfix 형태로 만들어 보고 실제로 만들어지 는지 확인해 봅시다.
Stack A,B를 만들고 A 에는 변수, B에는 연산자가 들어가게 합시다.
하나씩 읽어 볼까요?
‘(’이 나오는 군요. icp 이니까 우선순위 20이며 따라서 B에 무조건 push 되겠군요.
Stack A: null
Stack B : (
숫자 2가 오니 A에 push 되며, +가 오는데 이는 우선순위 12이며, 그 이전에 들어가 있는 연산자 ‘(’는 isp 이므로 우선순위 0 이군요. 따라서 +는 B에 push 되는군요. 다음처럼..
Stack A : 2
Stack B : ( +
숫자 3이 오니 A에 push 되고, * 가 오는데 이는 +보다 우선순위가 크죠? 따라서 B에 그냥 push 됩니다.
Stack A : 2 3
Stack B : ( + *
이제 숫자 4가 오니 A에 push 되고, ‘)’이 오는군요. ‘)’는 B에 실제로 push 되는 것이 아니라 ‘(’을 만날때까지 pop해서 A에 push 한다고 했죠? 따라서 +,*을 모두 pop하는군요.
Stack A : 2 3 4 * +
Stack B :
‘(’ 와 ‘)’는 실제로 Stack A 에 들어가지는 않고, 그저 연산자들이 pop 되는 순서를 조정함으로써 그 역할을 하는 것이죠.
이젠 ^ 이 오네요. B에 push 되고(아무값도 없으니 무조건 push 이죠?) 그리고 나서 1이 오네요. A에 push . 다음처럼..
Stack A : 2 3 4 * + 1
Stack B : ^
이젠 /가 오는데 ^보다 우선순위가 낮죠? 따라서 ^를 pop 한후 A에 push 하고. 자신은 B에 push 됩니다.
Stack A : 2 3 4 * + 1 ^
Stack B : /
남은 것은 (6*7) 뿐이군요. ‘(’이 B에 push 될 때는 icp 이므로 우선순위 20. 따라서 무조건 push 되고 . 6은 A에 push.
Stack A : 2 3 4 * + 1 ^ 6
Stack B : / (
*가 B에 들어갈려고 할 때, 보니까 ‘(’이 있으며 ‘(’은 이미 스택에 존재하는 값이니 우선순위 0으로 보면 되죠? 따라서 *는 그냥 push 됩니다. 그리고 7은 A에 push..
Stack A : 2 3 4 * + 1 ^ 6 7
Stack B : / ( *
마지막으로 ‘)’이 오는데 이는 ‘(’을 만날때까지 계속 pop해서 그 원소들을 A에 push 하죠?
여기선 달랑 * 뿐이군요.
Stack A : 2 3 4 * + 1 ^ 6 7 *
Stack B : /
모든 연산자 우선순위 처리가 끝났으니 Stack B에 남아있는 원소들을 차례대로 pop해서
A에 push하면 최종 결과가 나오는군요.
2 3 4 * + 1 ^ 6 7 * /
이 postfix 형태롤 한번 infix 형태로 바꿔볼까요? 가장 먼저 봐야 할것이 연산자 이므로
음..*가 맨 먼저 나오네요. 그 앞의 변수는 3와 4 이니. 3*4한 결과인 12가 대신 들어가겠군요.
2 12(3*4) + 1 ^ 6 7 * /
보니까 이젠 + 가 있군요. 그 바로 앞 두 변수로는 2 와 12 이군요. 이 둘을 더한 값 2+12, 즉 14가 그 대신 들어가겠군요.
14(2+3*4) 1 ^ 6 7 * /
이젠 ^ 이 나오는군요. 그 앞의 두 변수로는 14와 1이군요. 14^1, 즉 14가 그 대신 들어가겠죠?
14{ (2+3*4)^1 } 6 7 * /
이젠 * 가 나오며 그 바로 앞 두 변수로는 6과 7 이군요. 6*7한 결과, 즉 42가 그 대신 들어가겠죠?
14{ (2+3*4)^1 } 42(6*7) /
마지막 연산자로 / 이 오는군요
14를 42로 나누기 군요. 이를 식으로 쓰자면
(2+3*4)^1/(6*7) 이죠?
어떤가요? 이 방법대로 하니까 정말 괄호를 포함한 infix 형태가 postfix 형태가 되며
이를 다시 infix 형태로 바꿔봄으로써 확인했죠?
저는 이런생각이 드네요. 괄호를 어떻게 처리할까? 라고 사람들이 아주 많이 생각했으며
그 중 한사람이 고심 끝에 이와같은 원칙을 알아낸거라고...
그럴꺼라고... 전 머리나빠서 바로 이런 원칙을 발견해 낼수 없습니다. --;
여하튼.. 공학계산기에서 괄호처리는 지금까지 설명한 방법대로 하신다면 큰 무리없이
할 수 있을것이며 조금더 기능을 추가하자면 음수를 뜻하는 - 즉.
2 * -5 / 3 도 계산가능하게 할수 있지 않을까요?
-5는 ‘빼기 5’가 아니라 음수 5라는 뜻으로... 저는 빼기와 음수의 기호가 모두 ‘-’으로
동일해서 도저히 같은 기호로 이들을 구분할 수가 없어서 음수는 ‘~’로 표현했습니다.
어디서? 나중에 보시게될 최종 저의 공학계산기 소스에서..말이죠..
음수 ‘~’는 +,-와 같은 우선순위인 12로 두면 될것이며
~5 -3을 postfix 형태로 해보면
5~3- 이겠네요. 일반 연산자는 그 연산자 바로앞 두 변수를 pop해서 계산을 했는데
‘~’일 경우만 바로 앞 변수 하나만 pop해서 거기에 -1 곱하면 되겠죠?
일반 연산자는 두 개의 항이 있어야 하지만, 음수를 뜻하는 연산자는 단항연산자이잖아요.
뭐 그리 어렵지 않을 겁니다. sin, cos 등도 넣는다면 더 좋겠죠? 무리수도 넣고..
그건 여러분 스스로 해결하세요. 저도 해 보지 않았으니.. ^^;
자 그럼 최종 공학계산기 full 소스와 그 껍데기를 보시죠.
이것또한 450여 라인이나 되기에 완벽히 분석하려 하지 말고 스스로 만들고 참고만 하시기 바랍니다.
// Calculator.java 애플릿으로 만들었습니다.
// makePostFix 메소드 : postfix 형태로 만드는 메소드
// makeResult 메소드 : postfix 형태를 가지고 최종 결과는 얻는 메소드
import java.awt.*;
import java.applet.Applet;
import java.awt.event.*;
import java.lang.String;
import java.util.StringTokenizer;
import java.lang.StringBuffer;
class StackArray{
Object firstStack[];
int top;
StackArray(int size){
firstStack = new Object[size];
top = -1; // empty로 초기화
}
Object getItem(int index) { // index번째의 원소 리턴
return firstStack[index];
}
void push(Object ele) { // top에 원소 집어넣기
firstStack[++top] = ele;
}
Object peek() { // top의 원소 보기..
return firstStack[top];
}
Object pop() { // top의 원소 빼오기.
return firstStack[top--];
}
}
public class Calculator extends Applet implements ActionListener {
private String temp; // 버튼 값을 임시저장하기위해
private TextField mainText = new TextField("",30); // 입력창
private TextField postFixText = new TextField("",30); // postfix 창
private TextField resultText = new TextField("",30); // result 창.
private Button num1 = new Button(" 1 ");
private Button num2 = new Button("2");
private Button num3 = new Button("3");
private Button num4 = new Button("4");
private Button num5 = new Button("5");
private Button num6 = new Button("6");
private Button num7 = new Button("7");
private Button num8 = new Button("8");
private Button num9 = new Button("9");
private Button num0 = new Button("0");
private Button plus = new Button(" + ");
private Button minus = new Button("-");
private Button multi = new Button("*");
private Button divide = new Button("/");
private Button rest = new Button("%");
private Button square = new Button("^");
private Button openSymbol = new Button("(");
private Button closeSymbol = new Button(")");
private Button sign = new Button(" +/- "); // 더하기,빼기가 아니라 부호임.
private Button clear = new Button("CE"); // 방금 누른것만 지움
private Button clearAll = new Button("C"); // 전체 자료 지움
private Button equal = new Button("=");
private Label name = new Label(" Calculator ");
StackArray mStack; // postFix 했는 결과를 저장 , mainStack
StackArray rStack; // mStack를 가지고 계산한 값을 저장 , resultStack
public void init() {
temp = "";
mainText.setEnabled(false); // 사용자 임의로 텍스트필드의 값 수정 불가능하게함.
postFixText.setEnabled(false); // 사용자 임의로 텍스트필드의 값 수정 불가능하게함.
resultText.setEnabled(false); // 사용자 임의로 텍스트필드의 값 수정 불가능하게함.
Panel introPanel = new Panel(); // Calculator 라는 문구가 나오는 패널.
Panel textPanel = new Panel(); // 텍스트 창 패널
Panel numPanel = new Panel(); // 숫자 패널
Panel arithPanel = new Panel(); // 연산자 패널
Panel otherPanel = new Panel(); // 부호,지움,결과(즉,나머지다른것들)패널
Panel masterPanel = new Panel(); // 위의 3패널을 포함하는 패널
// 보기 좋게 하기 위해 색깔 첨가
setFont(new Font("Arial",5,11));
setBackground(Color.black);
introPanel.setBackground(Color.darkGray);
mainText.setBackground(Color.black);
postFixText.setBackground(Color.black);
resultText.setBackground(Color.black);
num1.setBackground(Color.yellow);
num2.setBackground(Color.yellow);
num3.setBackground(Color.yellow);
num4.setBackground(Color.yellow);
num5.setBackground(Color.yellow);
num6.setBackground(Color.yellow);
num7.setBackground(Color.yellow);
num8.setBackground(Color.yellow);
num9.setBackground(Color.yellow);
num0.setBackground(Color.yellow);
plus.setBackground(Color.green);
minus.setBackground(Color.green);
multi.setBackground(Color.green);
divide.setBackground(Color.green);
square.setBackground(Color.green);
rest.setBackground(Color.green);
openSymbol.setBackground(Color.green);
closeSymbol.setBackground(Color.green);
sign.setBackground(Color.orange);
clear.setBackground(Color.orange);
clearAll.setBackground(Color.orange);
equal.setBackground(Color.orange);
// 각 버튼의 이벤트 처리위해 아래와 같이함.
num1.addActionListener(this);
num2.addActionListener(this);
num3.addActionListener(this);
num4.addActionListener(this);
num5.addActionListener(this);
num6.addActionListener(this);
num7.addActionListener(this);
num8.addActionListener(this);
num9.addActionListener(this);
num0.addActionListener(this);
plus.addActionListener(this);
minus.addActionListener(this);
multi.addActionListener(this);
divide.addActionListener(this);
square.addActionListener(this);
rest.addActionListener(this);
openSymbol.addActionListener(this);
closeSymbol.addActionListener(this);
sign.addActionListener(this);
clear.addActionListener(this);
clearAll.addActionListener(this);
equal.addActionListener(this);
// numPanel에 각 숫자 버튼 추가함.
numPanel.setLayout(new GridLayout(4,3,2,8));
numPanel.add(num1);
numPanel.add(num2);
numPanel.add(num3);
numPanel.add(num4);
numPanel.add(num5);
numPanel.add(num6);
numPanel.add(num7);
numPanel.add(num8);
numPanel.add(num9);
numPanel.add(num0);
// arithPanel에 각 연산자 버튼 추가함
arithPanel.setLayout(new GridLayout(4,2,2,8));
arithPanel.add(plus);
arithPanel.add(minus);
arithPanel.add(multi);
arithPanel.add(divide);
arithPanel.add(rest);
arithPanel.add(square);
arithPanel.add(openSymbol);
arithPanel.add(closeSymbol);
// otherPanel 에 나머지 버튼 추가함
otherPanel.setLayout(new GridLayout(4,1,2,8));
otherPanel.add(sign);
otherPanel.add(clear);
otherPanel.add(clearAll);
otherPanel.add(equal);
introPanel.add(name); // calculator 라는 문구가 나오는 패널 추가
// textPanel에 3개의 텍스트 창 추가
textPanel.setLayout(new GridLayout(3,1));
textPanel.add(mainText);
textPanel.add(postFixText);
textPanel.add(resultText);
// masterPanel 에 numPanel,arithPanel , otherPanel 추가함
masterPanel.add(numPanel);
masterPanel.add(arithPanel);
masterPanel.add(otherPanel);
add(introPanel);
add(textPanel);
add(masterPanel);
}
int getPri(Object ob , boolean cs) { // 우선순위를 얻는 함수, cs는 icp or isp ..
String operator = (String)ob;
int pri = -1;
if ( operator.equals("+") )
pri = 12;
if ( operator.equals("-") )
pri = 12;
if ( operator.equals("*") )
pri = 13;
if ( operator.equals("/") )
pri = 13;
if ( operator.equals("%") )
pri = 13;
if ( operator.equals("~") ) // ~ 는 부호연산자..음수를 뜻함. 빼기와 구분위해..
pri = 15;
if ( operator.equals("^") )
pri = 14;
if ( operator.equals(")") )
pri = 19;
if ( operator.equals("(") ) {
if ( cs == true ) // icp를 묻는 경우
pri =20;
if ( cs == false ) // isp 를 묻는 경우
pri = 0;
}
return pri;
}
public void actionPerformed(ActionEvent e) {
showStatus("");
if ( e.getSource() == num1 ) {
temp = temp + "1" ;
mainText.setText(temp);
}
if ( e.getSource() == num2 ) {
temp = temp + "2" ;
mainText.setText(temp);
}
if ( e.getSource() == num3 ) {
temp = temp + "3" ;
mainText.setText(temp);
}
if ( e.getSource() == num4 ) {
temp = temp + "4" ;
mainText.setText(temp);
}
if ( e.getSource() == num5 ) {
temp = temp + "5" ;
mainText.setText(temp);
}
if ( e.getSource() == num6 ) {
temp = temp + "6" ;
mainText.setText(temp);
}
if ( e.getSource() == num7 ) {
temp = temp + "7" ;
mainText.setText(temp);
}
if ( e.getSource() == num8 ) {
temp = temp + "8" ;
mainText.setText(temp);
}
if ( e.getSource() == num9 ) {
temp = temp + "9" ;
mainText.setText(temp);
}
if ( e.getSource() == num0 ) {
temp = temp + "0" ;
mainText.setText(temp);
}
if ( e.getSource() == plus ) {
temp = temp + "+";
mainText.setText(temp);
}
if ( e.getSource() == minus ) {
temp = temp + "-";
mainText.setText(temp);
}
if ( e.getSource() == multi ) {
temp = temp + "*";
mainText.setText(temp);
}
if ( e.getSource() == divide ) {
temp = temp + "/";
mainText.setText(temp);
}
if ( e.getSource() == rest ) {
temp = temp + "%";
mainText.setText(temp);
}
if ( e.getSource() == square ) {
temp = temp + "^";
mainText.setText(temp);
}
if ( e.getSource() == sign ) { // 연속해서 두번누르면 없는것과 마찬가지이므로 코딩할게 많음.
String imsi = mainText.getText();
if ( imsi.length() != 0 ) {
String isOver = imsi.substring(imsi.length()-1,imsi.length());
if ( isOver.equals("~") ) // 이미 ~이 존재한다면 없애줌.
temp = imsi.substring(0,imsi.length()-1);
else // ~가 없다면 ~ 넣어줌.
temp = temp + "~";
mainText.setText(temp); // 텍스트 창에 표현.
}
else { // 입력시 맨 처음일땐 무조건 ~ 넣어줌.
temp = temp + "~";
mainText.setText(temp);
}
}
if ( e.getSource() == openSymbol ) {
temp = temp + "(" ;
mainText.setText(temp);
}
if ( e.getSource() == closeSymbol ) {
temp = temp + ")" ;
mainText.setText(temp);
}
if ( e.getSource() == equal) { // 결과나오게 하는 메소드 호출
try { // 예외 사항 처리..
makePostFix(); // postfix로 만들고
makeResult(); // 실제 계산 결과를 보여줌.
} catch (Exception exc) {
showStatus("예외사항 발생!"+exc);
}
}
if ( e.getSource() == clear ) { // 맨 끝에 입력한 것만 지워줌..즉 back-space
String imsi=mainText.getText();
temp = imsi.substring(0,imsi.length()-1); // 하나 없앤것 넣어줌.
mainText.setText(temp);
}
if ( e.getSource() == clearAll ) {
clearText(); // 모두 지우는 메쏘드 호출
mainText.setText(temp);
}
}
void clearText() {
temp = "";
mainText.setText(temp);
postFixText.setText(temp);
resultText.setText(temp);
showStatus("다시 시작!");
}
double getSquare(double x,double exp) { // 거듭제곱은 지원하지 않기에 만들어야함.
int i;
double temp=1;
for (i=1 ; i<=exp ; i++ ) {
temp = temp * x;
}
return temp;
}
void makePostFix() {
String inputData = mainText.getText(); // 입력한 수식을 inputData로함.
String nToken; // 토큰을 하나씩 받아와서 저장할려고..
StringTokenizer parser;
parser = new StringTokenizer(inputData,"+-*/^%()~",true);
int num = parser.countTokens(); // 각 원소 갯수를 알아냄.
StackArray mainStack = new StackArray(num); // 실제로 필요한 스택자료저장
StackArray tempStack = new StackArray(num); // +-/ 등을 임시 저장하기위해
String operators = "+-*/^%(~"; // ')'이 없는 이유는 특이하기에 따로 만들어야함.
while (parser.hasMoreTokens()) { // 토큰이 없을때까지 실행
nToken = parser.nextToken();
boolean isOperator = false; // 연산자인지 아닌지 판별. false는 연산자 아님을 뜻함.
for ( int i=0 ; i < operators.length() ; i++ ) {
if ( nToken.equals(operators.substring(i,i+1)) ) // 만약 nToken이 연산자이면 true!
isOperator = true;
}
if ( isOperator == true ) { // ')'을 제외한 연산자일경우 , 연산자 우선순위에 따라 처리..
while ( (tempStack.top >= 0) && getPri(nToken,true) <= getPri(tempStack.peek(),false) ) {
mainStack.push(tempStack.pop());
}
tempStack.push(nToken);
}
if ( nToken.equals(")") ) {
isOperator = true;
boolean isEnd = false;
while ( (tempStack.top >= 0) && isEnd == false ) {
if (getPri(tempStack.peek(),false)==0) isEnd = true; // '('이 나오면 끝(stop)
else mainStack.push(tempStack.pop()); // '('이 나올때까지 pop시켜서 push한다.
}
tempStack.pop(); // '('를 pop시켜서 지워준다. 괄호는 postfix에 들어가면 안되므로.
}
if ( isOperator == false) // 일반 숫자일 경우는 그냥 push한다.
mainStack.push(nToken);
}
while ( tempStack.top >= 0 ) {
// 일단 모든 parser에 관해 처리를 했다면 남아있는 것(tempStack)들을
// 모두 pop해서 mainStack에 push한다.
mainStack.push(tempStack.pop());
}
String userView="";
for (int i=0; i<=mainStack.top ;i++ ) {
userView = userView + mainStack.getItem(i);
// 화면에는 pop을 이용해서 보이게 할수 없으므로..처음부터 get..
}
postFixText.setText(userView);
mStack = mainStack; // Calculator 의 멤버변수에 저장해둠. 왜냐면 다른 메소드에서 접근해야 하므로..
}
void makeResult() {
rStack = new StackArray(mStack.top+1);
for ( int i=0; i <= mStack.top ; i++ ) {
Object t = mStack.getItem(i);
if ( t.equals("~") ) {
// 단항연산자이므로 하나만 pop시킨후 음수로 고친다.
double a = Double.valueOf((String)rStack.pop()).doubleValue();
a = -1 * a ;
rStack.push(a+"");
}
else if ( t.equals("+")||t.equals("-")||t.equals("*")||t.equals("/")||t.equals("%")||t.equals("^")) {
double latter = Double.valueOf((String)rStack.pop()).doubleValue();
//pop는 뒤에서부터 가져오는것이므로
double former = Double.valueOf((String)rStack.pop()).doubleValue();
// 먼저가져온것이 실제로 후자.
double temp = -1; // 계산결과를 저장하는 변수
if ( t.equals("+") )
temp = former+latter;
if ( t.equals("-") )
temp = former-latter;
if ( t.equals("*") )
temp = former*latter;
if ( t.equals("/") )
temp = former/latter;
if ( t.equals("%") )
temp = former%latter;
if ( t.equals("^") )
temp = getSquare(former,latter);
rStack.push(temp+"");
}
else {
rStack.push(t); // 연산자 아닐경우 그냥 push해줌.
}
}
resultText.setText(rStack.pop()+""); // rStack에는 오직 하나의 값.즉 결과값만 있으니까..pop
}
}