스택

개념

Last in Frist Out의 특징을 갖는 자료구조로, 먼저 들어간 값이 제일 마지막에 나오게 된다.

스택에서 값을 빼는 pop과, 스택에 값을 집어 넣는 push는 스택의 같은 방향에서 이루어진다.

 

구현 (C++)

#include <iostream>
using namespace std;
#define SZ 10

int stack[SZ];
int top = -1;

int isempty() // top이 -1이면 스택이 비어있다는 의미
{
	return (top==-1);
}

int isfull() // top이 스택의 크기와 같다면 스택이 가득 차있다는 의미
{
	return (top==SZ);
}

void push(int n)
{
	if(isfull()==1) return;
    top++;
    stack[top] = n;
    return;
}

int pop() 
{
	int tmp;
    if(isempty()==1) return -1;
    tmp = stack[top];
    top--;
    return tmp;
}

예제 https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

스택과 벡터가 거의 동일하기 때문에 스택 대신 벡터를 이용했다.

연산 기호가 나올 때까지 스택에 넣고, 연산기호가 나오면 스택에 있던 수를 기호에 맞게 연산한 후,

그 값을 다시 스택에 넣는다.

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

double result(double a, double b, char c)
{
    if(c=='+') return b+a;
    else if(c=='-') return b-a;
    else if(c=='*') return b*a;
    else if(c=='/') return b/a;
}

int main()
{
    vector<double> v;
    int n;
    cin>>n;
    string s;
    cin>>s;
    int arr[27];
    for(int i=0; i<n; i++) cin>>arr[i];
    for(int i=0; i<s.length(); i++)
    {
        if(s[i]>='A'&&s[i]<='Z') 
        {
            v.push_back(arr[s[i]-'A']);
        }
        else
        {
            double a=v.back();
            v.pop_back();
            double b=v.back();
            v.pop_back();
            double res = result(a,b,s[i]);
            v.push_back(res);
        }
    }
    printf("%.2f",v.back());
}