[자료구조] 스택(2)
스택의 응용 : 산술식 표현/변환
산술식 표현
산술식
- 수(양)의 간단한 성질 및 셈을 수학적으로 계산하여 표기하는 방식을 말함
산술식 7 + 3 => 피연산자 연산자 피연산자
연산자(operator)
- 프로그램의 산술식이나 연산식을 표현하고 처리하기 위해 제공되는 다양한 기호(산술 연산자: +, -, *등)를 말함
피연산자(operand)
- 연산(operation)에 참여하는 변수 또는 값을 말함
산술식의 내부 표현 방법
|
전위표기법(prefix) polish notation |
연산자 - 피연산자 - 피연산자 | x + 1 2 + 3 4 | LISP, Assembly |
| 중위(infix) 표기법 | 피연산자 - 연산자 - 피연산자 | (1 + 2) x (3 + 4) | C, JAVA |
|
후위(postfix) 표기법 |
피연산자 - 피연산자 - 연산자 | 1 2 + 3 4 + x | C(c++, a--) |
산술식 변환
산술식의 변환 방법(괄호 사용)
괄호를 사용한 중위 표현식의 전위/후위 표현 방법
- 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
- 각 연산자를 그에 대응하는 괄호의 전위(위쪽), 후위(오른쪽)으로 이동한다.
- 괄호를 제거한다.
산술식의 변환 방법(스택 사용)
스택을 사용하여 입력된 중위 표현식을 후위 표현식으로 변환 방법
- 연산식을 토큰 단위(한 문자)로 입력받아 피연산자일 경우 바로 출력한다.
- 연산자를 만나면 스택에 삽입(우선순위를 고려)한다.
- 스택에 삽입 <=> 스택에 저장된 연산자(ISP) < 현재 연산자(ICP)인 경우
- 스택에서 삭제한 후 삽입 <=> 스택에 저장된 연산자(ISP) >= 현재 연산자(ICP)인 경우
- 우측 괄호를 만나면 모든 연산자를 pop하거나 연산식을 다 읽은 경우 stack이 공백이 될 때까지 삭제한다.
산술식의 변환 예(스택 사용)
중위 표현식 : A*(B+C)/D를 후위 표현식으로 변환하는 프로그램
#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;
}
}
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=='-'){
return 1;
}
else{
return 0;
}
}
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;
}
실행 결과
중위 표현식:A*(B+C)/D
후위 표현식:ABC+*D/
스택의 응용 : 산술식 평가
산술식 평가
산술식(postfix) 평가 방법
산술식 평가 - 표현식(산술식)으로부터 값을 도출하는 과정을 말함
연산자 종류
- 단항 연산자 - (+3)
- 이항 연산자 - 3 + 4
- 삼항 연산자 - num2 = num1 ? 100 : 200;
후위 표현식 평가는 괄호가 필요없으며, 우선순위를 고려하지 않아도 됨
- 피연산자를 만나면 스택에 삽입한다.
- 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 삭제하여 연산하고, 연산결과를 다시 스택에 삽입한다.
- 1~2의 과정을 반복하여 수식이 끝나면, 마지막으로 스택에서 결과값을 삭제하여 출력한다.
Postfix 산술식 평가
후위 표현식 : 3 4 x 6 3 / - 를 평가하는 프로그램
#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;
}
실행 결과
후위 표현식 :34*63/-
후위 표현식 평가 결과값 = 10
다중 스택
다중 스택(multi-stack)
여러 개의 스택을 운용하는 경우로서 일반적으로 스택의 오버플로우 발생의 방지를 위해 사용되는 구조임
- 배열이나 연결리스트를 이용하여 표현할 수 있음
- 배열에서 두 개의 스택을 독립적으로 운영하면 단일 스택보다 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를 증가 함
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 i;
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;
}
실행결과
-----메뉴-----
1. 스택 A에 원소를 삽입
2. 스택 B에 원소를 삽입
3. 스택 A에서 원소를 삭제
4. 스택 B에서 원소를 삭제
5. 스택 A의 원소들을 출력
6. 스택 B의 원소들을 출력
7. 종료
연산에 해당되는 번호를 선택하세요 : 1
스택 A에 삽입할 원소를 입력 : 10
연산에 해당되는 번호를 선택하세요 : 1
스택 A에 삽입할 원소를 입력 : 20
연산에 해당되는 번호를 선택하세요 : 5
스택 A의 원소들:20 10
연산에 해당되는 번호를 선택하세요 :