스택을 이용한 문제

스택을 이용하여 중위표기식을 후위표기식으로 나타 내고 연산 하기

 

class ArrayStack {

private int top;

private int Size;

private char Array[];

 

public ArrayStack(int Size) {

top = -1;

this.Size = Size;

Array = new char[this.Size];

}

public boolean Empty() {

return (top == -1);

}

public boolean Full() {

return (top == Size - 1);

}

public void push(char item) {

if (Full())

System.out.println("Inserting fail! Array Stack is full!!");

else {

Array[++top] = item;

}

 

}

public char pop() {

if (Empty()) {

System.out.println("Deleting fail! Array Stack is empty!!");

return 0;

} else {

char item = Array[top--];

return item;

}

}

public void printStack() {

if (Empty())

System.out.println("Array Stack is empty!! %n %n");

else {

}

}

}

class intStack {

int numtop;

private int Size;

private int Num[];

 

public intStack(int Size) {

numtop = -1;

this.Size = Size;

Num = new int[this.Size];

}

public boolean Empty() {

return (numtop == -1);

}

public boolean Full() {

return (numtop == Size - 1);

}

public void push(int num) {

if (Full())

System.out.println("Inserting fail! Array Stack is full!!");

else {

Num[++numtop] = num;

}

}

public void countpush(int num) {

if (Full())

System.out.println("Deleting fail! Array Stack is empty!!");

else {

Num[++numtop] = num;

}

}

public int pop() {

if (Empty()) {

System.out.println("Deleting fail! Array Stack is empty!!");

return 0;

} else {

int num = Num[numtop--];

return num;

}

}

public int countpop() {

if (Empty()) {

System.out.println("Deleting fail! Array Stack is empty!!");

return 0;

} else {

int num = Num[numtop--];

 

return num;

}

}

}

class OptExp {

private String exp;

private int expSize;

private char testCh, openPair;

 

public void testPair(String exp) {

this.exp = exp;

 

expSize = this.exp.length();

ArrayStack A = new ArrayStack(expSize);

for (int a = 0; a < expSize; a++) {

testCh = this.exp.charAt(a);

switch (testCh) {

case '(':

case '{':

case '[':

A.push(testCh);

break;

case ')':

case '}':

case ']':

if (A.Empty())

System.out.println("괄호 틀림");

else {

openPair = A.pop();

if ((openPair == '(' && testCh != ')')

|| (openPair == '{' && testCh != '}')

|| (openPair == '[' && testCh != ']'))

System.out.println("괄호 틀림");

else

break;

}

}

}

if (A.Empty()) {

System.out.println("괄호 맞음");

} else {

System.out.println("괄호 틀림");

}

}

public char[] toPostfix(String infix) {

int j = 0;

char testCh;

exp = infix;

int expSize = this.exp.length();

char postfix[] = new char[expSize];

ArrayStack A = new ArrayStack(expSize);

char a = ' ';

 

for (int i = 0; i < expSize; i++) {

testCh = this.exp.charAt(i);

if (testCh == '+' || testCh == '-' || testCh == '*'

|| testCh == '/') {

postfix[j++] = a;

}

switch (testCh) {

case '0':

case '1':

case '2':

case '3':

case '4':

case '5':

case '6':

case '7':

case '8':

case '9':

postfix[j++] = testCh;

break;

case '+':

case '-':

case '*':

case '/':

A.push(testCh);

break;

case ')':

postfix[j++] = A.pop();

break;

default:

}

}

postfix[j] = A.pop();

return postfix;

}

public int toposteval(String infix) {

int a = 0, n = 0, x = 0, numSize = 0, opr1, opr2, postfix, postfix1, postfix2;

intStack num = new intStack(20);

intStack size = new intStack(20);

ArrayStack A = new ArrayStack(20);

for (int b = 0; b < expSize; b++) {

testCh = exp.charAt(b);

 

switch (testCh) {

case '0':

case '1':

case '2':

case '3':

case '4':

case '5':

case '6':

case '7':

case '8':

case '9':

n = testCh - '0';

num.push(n);

numSize++;

break;

case '+':

case '-':

case '*':

case '/':

A.push(testCh);

if (exp.charAt(b - 1) != ')' && exp.charAt(b + 1) != '(') {

size.countpush(numSize);

numSize = 0;

}

break;

case ')':

if (A.Empty())

break;

else {

if (numSize != 0) {

size.countpush(numSize);

numSize = 0;

}

x = 0;

int calcnum[] = new int[10];

while (!size.Empty()) {

int number = 0;

int temp = size.countpop();

for (a = 0; a < temp; a++) {

number += num.pop() * Math.pow(10, a);

}

if (number != 0)

calcnum[x++] = number;

}

if (calcnum[0] != 0) {

opr2 = calcnum[0];

opr1 = calcnum[1];

} else {

opr2 = num.pop();

opr1 = num.pop();

}

switch (A.pop()) {

case '+':

num.push(opr1 + opr2); break;

case '-':

num.push(opr1 - opr2); break;

case '*':

num.push(opr1 * opr2); break;

case '/':

num.push(opr1 / opr2); break;

}

}

}

}

postfix2 = num.pop();

postfix1 = num.pop();

switch (A.pop()) {

case '+':

num.push(postfix1 + postfix2); break;

case '-':

num.push(postfix1 - postfix2); break;

case '*':

num.push(postfix1 * postfix2); break;

case '/':

num.push(postfix1 / postfix2); break;

}

postfix = num.pop();

return postfix;

}

}

public class data04 {

 

public static void main(String[] args) {

 

OptExp opt = new OptExp();

char postfix[];

int result;

String exp = "(6*13)+(160/4)";

System.out.println("중위표기식 : " + exp);

opt.testPair(exp);

postfix = opt.toPostfix(exp);

System.out.print("후위 표기식 : ");

System.out.println(postfix);

result = opt.toposteval(exp);

System.out.println("연산결과 : " + result);

System.out.println("------------------------------------------");

 

exp = "(32*40)-(20+21)";

System.out.println("중위표기식 : " + exp);

opt.testPair(exp);

postfix = opt.toPostfix(exp);

System.out.print("후위 표기식 : ");

System.out.println(postfix);

result = opt.toposteval(exp);

System.out.println("연산결과 : " + result);

System.out.println("------------------------------------------");

 

exp = "(320*2)+(200/10)";

System.out.println("중위표기식 : " + exp);

opt.testPair(exp);

postfix = opt.toPostfix(exp);

System.out.print("후위 표기식 : ");

System.out.println(postfix);

result = opt.toposteval(exp);

System.out.println("연산결과 : " + result);

System.out.println("------------------------------------------");

}

 

}