5. Stack

Stack

입출구가 동일하여 가장 나중에 들어온 데이터가 가장 빨리 나가는 자료구조입니다. LIFO(Last-in-First-Out) 목록이라고도 합니다.

 

구현 (배열)

• N개의 항목을 스택에 저장하기 위해 배열 s[ ]을 사용합니다.
  • push(): s[N]에 새로운 항목을 추가합니다.
  • pop(): remove item from s[N-1]에 있던 항목을 제거 합니다.

Defect. capacity이상으로 항목의 개수가 들어오면 스택 오버플로우가 일어납니다.

=> resize로 해결

 

기능

Stack CreateStack (maxStackSize)
bool IsFull (Stack stack)
bool IsEmpty (Stack stack)
void Push (Stack stack, item)
void Pop (Stack stack)
int size(Stack stack)

 

• Stack CreateStack (int maxStackSize)

// A structure to represent a stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

struct Stack* createStack (int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

 

• bool isFull(Stack stack)

bool isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

 

• bool isEmpty (Stack stack)

bool isEmpty (struct Stack* stack) {
    return stack->top == -1;
}

 

• void push (struct Stack* stack, int item)

void push (struct Stack* stack, int item) {
    if (isFull(stack)) return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

 

• void pop (struct Stack* stack)

void pop(struct Stack* stack) {
    if (isEmpty(stack)) return;
    stack->array[stack->top--];
}

 

• int size(struct Stack* stack)

int size(struct Stack* stack) {
    return stack->top+1;
}

 

• void listStack(struct Stack* stack)

void listStack(struct Stack* stack) {
    for (int i = 0; i <= stack->top; i++) {
        printf("%d ", stack->array[i]);
    }
    printf("\n");

}

 

 

스택의 적용

1. 중위 표기법(Infix)을 후위표기법(Postfix)으로 - Arithmetic expression evaluation

• 중위 표기법: 피연산자(숫자) 사이에 연산자(덧셈, 곱셈, 뺄셈, 나눗셈)가 있는 식 ex) 1+3*2+4/2
• 전위 표기법: 연산자가 피연산자 앞에 나오는 방식.
  1. 연산자 우선순위에 맞게 괄호를 쳐줍니다.
  2. ((1+(2*3))+(1+(2/2)))
  3. 이 괄호안에 있는 연산자들을 앞으로 빼줍니다.
  4. +((+1*(23))(+1/(22)))
  5. 괄호를 모두 없애줍니다.
  6. ++1*23+1/22
• Ex) 1+2*3+1+2/2
• 후위 표기법: 연산자가 뒤에 오는 수식
  1. 연산자 우선순위에 맞게 괄호를 처줍니다.
  ((1+(2*3)+((4+2)/2)))
  2. 괄호에 있는 연산자를 괄호뒤로 빼줍니다.
  ((1(23)*)+((42)+2)/))+
  3. 괄호를 모두 없애면 후위 표기로 바뀌게 되는 겁니다.
  123*+42+2/+
• Ex) 1+2*3+(4+2)/2

 

알고리즘1 (스택)

(1+ ( ( 2 + 3 ) * ( 4 * 5 ) ) )

• Value stack, operator stack 을 만든다.
• "(" 는 무시한다.
• ")"
  • 연산자 하나와 숫자 두개를 pop
  • pop된 연산자 하나와 숫자 두개의 연산결과를 value stack에 push

 

code (c++)

#include <cstdio>
#include <string>
#include <stack>
#include <iostream>

using namespace std;

bool isNumber(char c) {
    if (c == '0' || c == '1' || c == '2' || c == '3' || c == '4' || c == '5' || c == '6' || c == '7' || c == '8' || c == '9') return true;
    else return false;
}

int main() {
    stack <int> num;
    stack <char> op;
    string infix;
    cin >> infix;

    for (int i = 0; i < infix.length(); i++) {
        if (infix[i] == '(') continue;
        else if (isNumber(infix[i])) num.push((infix[i]) - '0');
        else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') op.push(infix[i]);
        else {
            int result, n1, n2;
            char oper;
            n1 = num.top();
            num.pop();
            n2 = num.top();
            num.pop();
            oper = op.top();
            op.pop();

            if (oper == '+') result = n1+n2;
            else if (oper == '-') result = n1-n2;
            else if (oper == '*') result = n1*n2;
            else result = result = n1/n2;
            
            num.push(result);
        }
    }
    
    cout << "result: " << num.top() << "\n";
    return 0;
}

 

 

후위 표기법 예제

 

 

알고리즘2 (스택)

infix: a – (b + c * d) / e

We use a stack.

1. When an operand is read, output it.
2. When an operator is read,
   1. Pop until the top of the stack has an element of lower precedence.
   2. Then push it.
3. When ) is found, pop until we find the matching (.
4. ( has the lowest precedence when in the stack but has the highest precedence when in the input.
5. When we reach the end of input, pop until the stack is empty.

 

 

 

2. 후위표기법(Postfix)을 중위표기법(Infix)으로 - Arithmetic expression evaluation

알고리즘 (스택)

피연산자 스택 한개만 사용

1. 피연산자가 나오면 스택에 쌓는다.
2. 연산자가 나오면 피연산자 스택에서 상위 두개를 pop
3. 중위표기식으로 바꾼후 괄호로 감싸고 스택에 push

 

Ex) abc-d+/ea-\*c\*

code (c++)