JavaTutorials

스택을 이용한 계산기

음,,, 우선 주어진 수식을 스택을 이용하여 후위표기법으로 바꾸신후
다시 이를 스택을 이용하여 연신을 하면 됩니다...

- . 중위표기법(infix)을 후위표기법(postfix)으로 바꾸는 법
1. ‘(‘를 만나면 스택에 푸시한다.
2. ‘)’를 만나면 스택에서 ‘(‘가 나올 때까지 팝하여 출력하고 ‘(‘는 팝하여 버린다.
3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지
팝하여 출력한 뒤에 자신을 푸시한다.(우선순위가 같거나 높은것은 팝한다.)
4. 피연산자는 그냥 출력한다.
5. 모든 입력이 끝나면 스택에 있는 연산자들을 모두 팝하여 출력한다.

- Postfix로 표시된 수식을 스택을 이용하여 계산하는 과정
1. token하나 읽어 피연산자면 스택에 넣는다.
2. 연산자이면 필요한 수 만큼 피연산자를 스택에서 커낸 후 연산을 수행하고 다시 스택에 넣는다.
3. 위의 과정을 반복하면 수식의 결과는 스택의 맨 아래에 남게 된다.

아래의 예제를 참고하세요~

스택은 이미 만들어져 있는 클래스를 쓰셔도 되나, 여기서는
별도로 구성하였습니다..

/* ArrayStack */

import java.util.EmptyStackException;

interface Stack {
public boolean isEmpty();
public Object peek();
public void push(Object theObject);
public Object pop();
}

public class ArrayStack implements Stack {
int top; // current top of stack
Object [] stack; // element array

/* create a stack with the given initial capacity */
public ArrayStack(int initialCapacity) {
if (initialCapacity < 1)
throw new IllegalArgumentException
("initialCapacity must be >= 1");
stack = new Object [initialCapacity] ;
top = -1;
}

/** create a stack with initial capacity 10 **/
public ArrayStack() {
this(10);
}
/** return true if stack is empty */
public boolean isEmpty( ) {
return top == -1;
}
/** return top element of stack
* throw EmptyStackException when the stack is empty */
public Object peek() {
if (isEmpty() )
throw new EmptyStackException();
return stack[top];
}

/** add theElement to the top of the stack */
public void push(Object theElement) {
// increase array size if necessary
if (top == stack.length - 1) ensureCapacity();

// put theElement at the top of the stack
stack[++top] = theElement;
}

/** remove top element of stack and return it
* throw EmptyStackException when the stack is empty */
public Object pop() {
if (isEmpty())
throw new EmptyStackException();
Object topElement = stack[top];
stack[top--] = null; // enable garbage collection
return topElement;
}

private void ensureCapacity() {
Object[] larger = new Object[stack.length*2];

for (int index=0; index < stack.length; index++)
larger[index] = stack[index];

stack = larger;
}

public String toString() {
if (isEmpty())
return "<empty stack>";
String result = "<stack :";
for (int i = top; i >= 0; i--)
result += stack[i] + " ";
return result + ">";
} // end toString
}

-----------------------------------

-----------------------------------

/* Calc.java */

/**
* Calc.java
*스택을 이용하여 중위표현을 후위표현으로 바꾸는 메소드
*후위표기 수식을 스택을 이용한 연산을 수행하는 메소드
* 수식등의 괄호가 맞는지 확인하는 메소드
*/
class Calc {
//-------------------------------------------------------------------
//스택을 이용하여 중위표현을 후위표현으로 바꾸는 메소드
//-------------------------------------------------------------------
String postfix(String infixExp) {
Double value;
//숫자의 끝임을 알려주는 flag
//소수점 수식도 처리하기 위해서...
boolean endOfNumber = false;
String postfixExp = new String();
ArrayStack stk = new ArrayStack();

for(int i = 0; i < infixExp.length(); i++)
{
switch(infixExp.charAt(i))
{
//피연산자는 그대로 출력한다.
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
postfixExp = postfixExp.concat(infixExp.charAt(i)+"");
endOfNumber = true;
break;
//왼쪽괄호인 경우에는 스택에 push 한다.
case '(':
if(endOfNumber == true) {
postfixExp = postfixExp.concat(" ");
endOfNumber = false;
}

stk.push(new Character('('));
break;
//우측괄호인 경우 좌괄호가 나올때까지 pop하여 출력하고
//좌괄호는 pop하여 버린다.
case ')':
if(endOfNumber == true) {
postfixExp = postfixExp.concat(" ");
endOfNumber = false;
}
while(((Character)stk.peek()).charValue() != '(' )
postfixExp = postfixExp.concat(((Character)stk.pop()).toString());
Object openParen = stk.pop();
break;
case '+':
case '-':
case '*':
case '/':
if(endOfNumber == true) {
postfixExp = postfixExp.concat(" ");
endOfNumber = false;
}
//연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지
//팝하여 출력한 뒤에 자신을 푸시한다.(우선순위가 같거나 높은것은 팝한다.)
while ( !stk.isEmpty() && ((Character)stk.peek()).charValue() != '('
&& getPrec(infixExp.charAt(i)) <= getPrec(((Character)stk.peek()).charValue()) ) {
postfixExp = postfixExp.concat(((Character)stk.pop()).toString());
}
stk.push(new Character(infixExp.charAt(i)));
break;
}
}

if(endOfNumber == true) {
postfixExp = postfixExp.concat(" ");
endOfNumber = false;
}

//모든 작업이 끝나면 스택에 있는 연산자들을 모두 팝하여 출력한다.
while( !stk.isEmpty()) {
postfixExp = postfixExp.concat(((Character)stk.pop()).toString());
}

System.out.println(postfixExp);

return postfixExp;
}

//----------------------------------------------------------------------
//후위표기 수식을 스택을 이용한 연산을 수행하는 메소드
//----------------------------------------------------------------------
Double result(String postfixExp) {
Double value, buffer;
String temp = new String();
ArrayStack stk = new ArrayStack();

for(int i=0; i<postfixExp.length(); i++) {
switch(postfixExp.charAt(i)) {

case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
//여기까지는 아직 공백을 만나지 않았으므로 수식의 끝이 아니다.
temp = temp.concat(postfixExp.charAt(i)+"");
break;
case ' ':
//공백을 만나서야 비로서 수식을 스택에 넣는다.
//공백을 만나기전에 수식이 여러개 있었다면 temp에 붙어서 저장되어 있다.
stk.push(new Double(temp));
temp = new String();
break;
case '+':
value = new Double(((Double)stk.pop()).doubleValue() + ((Double)stk.pop()).doubleValue());
stk.push(value);
break;
case '-':
buffer = new Double(((Double)stk.pop()).doubleValue());
value = new Double(((Double)stk.pop()).doubleValue() - buffer.doubleValue());
stk.push(value);
break;
case '*':
value = new Double(((Double)stk.pop()).doubleValue() * ((Double)stk.pop()).doubleValue());
stk.push(value);
break;
case '/':
buffer = new Double(((Double)stk.pop()).doubleValue());
value = new Double(((Double)stk.pop()).doubleValue() / buffer.doubleValue());
stk.push(value);
break;
}
}
return (Double)stk.peek();
}

//------------------------------------------
//연산자의 우선순위를 Return
//------------------------------------------
int getPrec(char op) {
int prec = 0;
switch (op) {
case '+':
case '-':
prec = 1;
break;
case '*':
case '/':
prec = 2;
break;
}
return prec;
}

//-----------------------------------------
//괄호의 정확성 검사
//-----------------------------------------
static boolean bracketsBalance (String exp) {
ArrayStack stk = new ArrayStack(exp.length() +1);
for (int i = 0; i < exp.length(); i++) {
//Scan across the expression
char ch = exp.charAt(i);
if ( ch== '[' || ch == '(' ) {
stk.push( new Character(ch));
}
else if(ch == ']' || ch == ')') {
//empty means brackets unmatched
if (stk.isEmpty()) return false;
char charFromStack = ((Character)stk.pop()).charValue();
if ( ch == ']' && charFromStack != '['
|| (ch == ')' && charFromStack != '(') )
return false;
} // end if
} // end for loop
return stk.isEmpty(); //empty means matched, else unmatched
}
}
----------------------------------------

/* Main.java */

class Main {
public static void main(String args[]) {
if (args.length < 1) {
System.out.println("Usage: java Postfix [infix expression]\n");
return;
}
String infixExp = args[0];
Calc c = new Calc();
if (!c.bracketsBalance(infixExp)){
System.out.println("괄호를 정확히 하세요~");
System.exit(1);
}
String postfixExp = c.postfix(infixExp);
Double result = c.result(postfixExp);
System.out.println("The postfix expression for "+ infixExp +" is " + postfixExp);
System.out.println("The result = "+result);
}
}

class HDTV implements Comparable {
 private int size;
 private String brand;
 
 public HDTV(int size, String brand){
  this.size = size;
  this.brand = brand;
 }
 
 public int getSize() {
  return size;
 }
 
 public void setSize(int size) {
  this.size = size;
 }
 
 public String getBrand() {
  return brand;
 }
 
 public void setBrand(String brand) {
  this.brand = brand;
 }
 
 @Override
 public int compareTo(Object obj) {
  if (!(obj instanceof HDTV)) {
   throw new ClassCastException("Invalid object");
  }
  int size = ((HDTV) obj).getSize();
 
  if (this.getSize() > size)
   return 1;
  else if (this.getSize() < size)
   return -1;
  else
   return 0;
 }
}
 
public class Main {
 public static void main(String[] args) {
  HDTV tv1 = new HDTV(55, "Samsung");
  HDTV tv2 = new HDTV(60, "Sony");
  if(tv1.compareTo(tv2)>0){
   System.out.println(tv1.getBrand() + " is better.");
  }else{
   System.out.println(tv2.getBrand() + " is better.");
  }
 }
}

//**********************************************************************

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
class HDTV {
 private int size;
 private String brand;
 
 public HDTV(int size, String brand){
  this.size = size;
  this.brand = brand;
 }
 
 public int getSize() {
  return size;
 }
 
 public void setSize(int size) {
  this.size = size;
 }
 
 public String getBrand() {
  return brand;
 }
 
 public void setBrand(String brand) {
  this.brand = brand;
 }
}
 
class SizeComparator implements Comparator{
 
 @Override
 public int compare(Object o1, Object o2) {
  int tv1Size = ((HDTV)o1).getSize();        
        int tv2Size = ((HDTV)o2).getSize();
 
        if(tv1Size > tv2Size){
         return 1;
        }else if(tv1Size < tv2Size){
         return -1;
        }else{
         return 0;
        }
 }
 
}
public class Main {
 public static void main(String[] args) {
  HDTV tv1 = new HDTV(55, "Samsung");
  HDTV tv2 = new HDTV(60, "Sony");
  HDTV tv3 = new HDTV(42, "Panasonic");
 
  ArrayList<HDTV> al = new ArrayList<HDTV>();
  al.add(tv1);
  al.add(tv2);
  al.add(tv3);
 
  Collections.sort(al, new SizeComparator());
  for(HDTV a: al){
   System.out.println(a.getBrand());
  }
 }
}

JavaTutorials

2013년 10월 17일 목요일

스택을 이용한 텍스트 계산기... (자바 스택 계산기)

Set 인터페이스

java.lang.Runtime#getRuntime()

Singleton Pattern Used in Java Stand Library

Example of Sorting Arrays

ArrayListSort

Comparable vs Comparator in Java