스택 응용
산술식 표현
- 산술식 : 수(양)의 간단한 성질 및 셈을 수학적으로 계산하여 표기하는 방식을 말함.
- 연산자(operator) : 프로그램의 산술식이나 연산식을 표현하고 처리하기 위해 제공되는 다양한 기호(산술 연산자 : +, -, *등)을 말함
- 피연산자(operand) : 연산(operation)에 참여하는 변수 또는 값을 말함
산술식의 내부 표현 방법
산술식 변환
산술식의 변환 방법(괄호)
괄호를 사용한 중위 표현식의 전위/후위 표현 방법
- 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현
- 각 연산자를 그에 대응하는 괄호의 전위(왼쪽), 후위(오른쪽)으로 이동
- 괄호를 제거한다
산술식의 변환 방법(스택 사용)
스택을 사용하여 입력된 중위 표현식을 후위 표현식으로 변환 방법
#include <stdio.h>
#include <stdlib.h> //exit() 처리
#include <ctype.h> //isdigit(char) 처리
#include <string.h>
#define SIZE 100
char stack[SIZE];
int top =-1;
void push(char item){ //스택의 삽입 연산
if(top >= SIZE-1 ){
printf("\n스택 오버플로우.");}
else{
top = top+1;
stack[top] = item; }
}중위 표현식 : A*(B+C)/D를 후위 표현식으로 변환하는 프로그램
char pop(){ //스택의 삭제 연산
char item ;
if(top <0){
printf("스택 언더플로우 - 괄호에 의한 잘못된 중위 표현식:(((a+b)*c)”);
getchar();
exit(1 ); //오류 메시지 종료
}
else{
item = stack[top];
top = top-1;
return(item);
}
}반응형
int is_operator(char symbol){ //기호가 연산자이면1을, 그렇지 않으면0을 반환
if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' ||
symbol =='-'){
return1;}
else{
return0; }
}
int precedence(char symbol){ //연산자 우선순위 값 할당
if(symbol == '^'){
return(3);}
else if(symbol == '*' || symbol == '/'){
return(2 );}
else if(symbol == '+' || symbol == '-'){
return(1 );}
else{
return(0);}}void InfixToPostfix(char infix_exp[], char postfix_exp[]){ //중위 표현식 변환
int i, j;
char item;
char x;
push('('); //'(' 를 스택에 push
strcat(infix_exp,")"); // ')' 를 중위 표현식에 추가
i=0;
j=0;
item=infix_exp[i]; //초기화
while(item != '\0'){ //중위 표현식이 끝날 때까지 반복
if(item == '('){ //좌측 괄호를 스택에 삽입
push(item);
}
else if( isdigit(item) || isalpha(item)){ //좌측 괄호의 숫자, 알파벳 판단
postfix_exp[j] = item; //item을 배열 postfix-exp[]에 추가(출력)
j++;
}
else if(is_operator(item) == 1 ){ //item이 연산자인 경우, isp와 icp를 고려
x=pop();
while(is_operator(x) == 1 && precedence(x)>=precedence(item)){
postfix_exp[j] = x;
j++;
x = pop();
}
push(x);
push(item);
}
else if(item == ')'){ //현재의 기호가 ')'이면 ‘(＇를 만날 때까지 pop
x = pop();
while(x != '('){
postfix_exp[j] = x; j++;
x = pop();}
else{
printf("\n잘못된 중위 표현식\n");
getchar();
exit(1 );
}
i++;
item = infix_exp[i]; //중위 표현식의 다음 심볼을 읽음
} //while문 종료
postfix_exp[j] =‘\0';//후위 표현식 마지막에 '\0'를 추가
}int main(){
char infix[SIZE], postfix[SIZE]; // 중위 표현식과 후위 표현식을 선언
printf("\n중위 표현식 : ");
gets(infix); //표준 입력으로 들어온 문자열을 저장
InfixToPostfix(infix, postfix);
printf("후위 표현식 : ");
puts(postfix);
return 0;
}
result
중위 표현식 : A*(B+C)/D
후위 표현식 : ABC+*D/
스택 응용 : 산술식 평가
산술식(postfix) 평가 방법
- 산술식 평가 : 표현식(산술식)으로부터 값을 도출하는 과정
- 연산자 종류
- 단항 연산자 : (+3)
- 이항 연산자 : 3+4
- 삼항 연산자 : num2 = num1 ? 100 : 200;
- 후위 표현식 평가는 괄호가 필요없으며 우선 순위를 고려하지 않아도 됨
- 피연산자를 만나면 스택에 삽입한다.
- 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 삭제하여 연산하고, 연산결과를 다시 스택에 삽입한다
- 1-2의 과정을 반복하여 수식이 끝나면, 마지막으로 스택에서 결과값을 삭제하여 출력한다
#include <stdio.h>
#define MAX 20
typedef struct stack{
int data[MAX];
int top;
}stack;
int evaluate(char x, int op1, int op2 ){ //연산자에 따른 수식 평가
if(x=='+') return (op1+op2 );
if(x=='-') return (op1-op2 );
if(x=='*') return (op1*op2 );
if(x=='/') return (op1/op2 );
if(x=='%') return (op1%op2 );
}void init(stack *s){ // 스택 top 포인터의 초기화
s->top=-1;
}
int empty(stack *s){ //스택의 empty 검사
if(s->top==-1 )
return(1 );
return(0);
}
int full(stack *s){ // 스택의 오버플로우 검사
if(s->top==MAX-1 )
return(1 );
return(0);
}void push(stack *s, int x){ // 스택에 x(피연산자)를 push
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s){ //스택에서 피연산자를 pop
int x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}int main(){
stack s;
char x;
int op1,op2,val;
init(&s);
printf("\n후위 표현식 :");
while((x=getchar())!='\n'){ //한 문자씩 후위 표현식을 읽음
if(isdigit(x))
push(&s, x-48); //x-48은 ASCII의 부작용을 제거하기 위함
else{ //피연산자이면 스택에 2개의 피연산자를 pop
op2=pop(&s);
op1=pop(&s);
val=evaluate(x,op1,op2 );
push(&s, val); //계산 결과를 스택에 push
}
} val=pop(&s); //평가 결과값
printf("\n후위 표현식 평가 결과값 = %d", val);
return 0;
}
result
후위 표현식 :34*63/-
후위 표현식 평가 결과값 = 10
다중 스택
여러 개의 스택을 운용하는 경우로서 일반적으로 스택의 오버플로우 발생의 방지를 위해 사용되는 구조
- 배열이나 연결리스트를 이용하여 표현할 수 있음
- 배열에서 두 개의 스택을 독립적으로 운영하면 단일 스택보다 2배의 공간을 활용할 수 있음(오버플로우화 현상 감소)
1차원 배열로 2개 스택의 운영 방법
- 삽입 : stack-1은 stack[m-1] 방향으로 top-1을 증가하고 stack-2는 stack[0]방향으로 top-2를 감소함
- 삭제 : stack-1은 stack[0] 방향으로 top-1을 감소하고 stack-2는 stack[m-1] 방향으로 top-2를 증가함
단일 배열의 다중 스택(multi-stack)
1차원 배열로 2개의 스택 운영 프로그램
#include <stdio.h>
#include <malloc.h>
#define MAX 10
int stack[MAX], topA =-1, topB = MAX;
void push_stackA(int val){ //스택A에 원소 삽입
if(topA == topB-1 )
printf("\n 스택 오버플로우");
else{
topA=topA+1;
stack[topA] = val;
}
}int pop_stackA(){ //스택A에서 원소 삭제
int val;
if(topA ==-1 ){
printf("\n 스택 언더플로우");}
else{
val = stack[topA];
topA=topA-1; }
return val;}
void display_stackA(){ //스택A의 원소들을 출력
int ;
if(topA ==-1 )
printf("\n 스택이 비었음");
else{
for(i = topA;i >= 0;i--)
printf("\t %d", stack[i]);}
}void push_stackB(int val){//스택B에 원소 삽입
if(topB-1 == topA){
printf("\n 스택 오버플로우");}
else{
topB=topB-1;
stack[topB] = val;}
}
int pop_stackB(){//스택B에서 원소 삭제
int val;
if(topB == MAX){
printf("\n 스택 언더플로우");}
else{
val = stack[topB];
topB=topB+1;}
}
void display_stackB(){//스택B의 원소들을 출력
int i;
if(topB == MAX)
printf("\n 스택이 비었음");
else{
for(i = topB;i < MAX;i++)
printf("\t %d", stack[i]);}
}
int main(){
int option, val;
printf("\n -----메뉴----- ");
printf("\n 1. 스택A에 원소를 삽입");
printf("\n 2. 스택B에 원소를 삽입");
printf("\n 3. 스택A에서 원소를 삭제");
printf("\n 4. 스택B에서 원소를 삭제");
printf("\n 5. 스택A의 원소들을 출력");
printf("\n 6. 스택B의 원소들을 출력");
printf("\n 7. 종료");
do{
printf("\n 연산에 해당되는 번호를 선택하세요 : ");
scanf("%d", &option);
switch(option){
case 1: printf("\n 스택A에 삽입할 원소를 입력 :");
scanf("%d", &val);
push_stackA(val);
break;
case 2: printf("\n 스택B에 삽입할 원소를 입력 :");
scanf("%d",&val);
push_stackB(val);
break;
case 3: printf("\n 스택A에서 삭제된 원소 = %d", val);
pop_stackA();
break;
case 4: printf("\n 스택B에서 삭제된 원소 = %d", val);
pop_stackB();
break;
case 5: printf("\n 스택A의 원소들 :\n");
display_stackA();
break;
case 6: printf("\n 스택B의 원소들 :\n");
display_stackB();
break;
}
} while(option != 7);
return 0;
}result
-----메뉴-----
1. 스택A에 원소를 삽입
2. 스택B에 원소를 삽입
3. 스택A에서 원소를 삭제
4. 스택B에서 원소를 삭제
5. 스택A의 원소들을 출력
6. 스택B의 원소들을 출력
7. 종료
연산에 해당되는 번호를 선택하세요 :1
스택A에 삽입할 원소를 입력 : 10
연산에 해당되는 번호를 선택하세요 :1
스택A에 삽입할 원소를 입력 : 20
연산에 해당되는 번호를 선택하세요 :5
스택A의 원소들:
20 10
연산에 해당되는 번호를 선택하세요:
1차원 배열로 스택 n개를 운영하는 경우(균등 분배, 차등 분배)
균등 분배 ( stack[m]에 대해 n개의 스택을 표현)
- 각 스택 i에 대하여 b[i]는 그 스택의 최하위 요소보다 하나 작은 위치를 나타냄
- 각 스택의 t[i] (1 <= i <= n)는 스택 i의 최상위 요소를 나타냄
- i번째 스택의 공백상태는 b[i] = t[i]
- i번째 스택의 오버플로우 상태는 t[i] = b[i+1]
다중 스택의 삽입에서 오버플로 해결 방법
스택i와 스택i+1이 만나는 경우 오버플로 발생
학습 정리
- 스택은 산술식 변환이나 평가에 활용가능
- 다중 스택은 여러 개의 스택을 운용하는 경우로서 일반적으로 스택의 오버플로우 발생을 방지하기 위해 사용되는 자료구조이다
- 단일 스택은 오버플로우 발생 시 실제 작업에 필요한 자료를 사용할 수 없으며, 중간에 작업을 중단하고 배열의 크기를 다시 재 선언해야 한다
- 다중 스택은 오버플로우 발생 시 스택의 많은 요소들이 이동 및 재 배열되어야 하는 문제 점(repacking 작업)이 있으며 비순차표현(연결구조)으로 구현하여 해결할 수 있다.
반응형