OI退役笔记-007：数据结构专题-栈

栈

栈是一种先进先出的数据结构
实现

typedef int stype;
stype stack_base[10010];
int length = 0;

void push(stype val)
{
	stack_base[length++] = val;
}

bool empty()
{
	return length();
}

int pop()
{
	if (!empty())
		return --length();
	return -1;
}

void clear()
{
	length = 0;
}

stype top()
{
	return stack_base[length - 1];
}

这是栈的基本实现，但 C++ 的 STL 里提供了栈的实现，在竞赛中可直接使用。

例题

实现：遇见左括号压栈，遇到右括号时，如果栈非空，则弹栈一次。若栈为空，则式子非法。在扫描所有字符后，若栈非空，则式子也非法。

代码：

#include <cstdio>
#include <stack>
 
std::stack<char> s;
char c;
 
int main()
{
    while (c != '@')
    {
        scanf("%c", &c);
        if (c == '(')
        {
            s.push('(');
        }
        else if (c == ')')
        {
            if (s.empty())
                return printf("NO"), 0;
            else
                s.pop();
        }
    }
     
    if (!s.empty()) return printf("NO"), 0;
    printf("YES");
}

相较上题，当遇到 ‘]’ 时，左边为 ‘[’ 则弹栈一次，否则非法；遇到 ‘)’ 同理

#include <cstdio>
#include <stack>
 
std::stack<char> s;
char c;
 
int main()
{
    while (scanf("%c", &c) != EOF)
    {
        if (c == '(' || c == '[')
        {
            s.push(c);
        }
        else if (c == ')' || c == ']')
        {
            if (s.empty())  return printf("Wrong"), 0;
            else
            {
                if ((s.top() != '(' && c == ')') || (s.top() != '[' && c == ']'))   return printf("Wrong"), 0;
                s.pop();
            }
        }
    }
     
    if (!s.empty()) return printf("Wrong"), 0;
    printf("OK");
}

这个相较上题，有多了一个括号的优先级问题，可用数组模拟。

#include <cstdio>
#include <stack>
#include <iostream>
#include <string>
 
std::stack<char> s;
std::string str;
char ad[128];
char f[128];
 
void clear()
{
    while (!s.empty())  s.pop();
}
 
bool b;
int main()
{
    ad['<'] = 1;
    ad['('] = 2;
    ad['['] = 3;
    ad['{'] = 4;
    f['>'] = '<';
    f[')'] = '(';
    f[']'] = '[';
    f['}'] = '{';
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        b = 0; 
        std::cin >> str;
        for (int j = 0; j < str.length(); ++j)
        {
            if (str[j] == '>' ||
                str[j] == ')' ||
                str[j] == ']' ||
                str[j] == '}')
            {
                if (s.empty())  {
                printf("NO\n");
                b = 1;
                break;}
                if (s.top() != f[str[j]])
                {
                    printf("NO\n");
                b = 1;
                break;}
                s.pop();
            }
            else if (str[j] == '<' ||
                    str[j] == '(' ||
                    str[j] == '[' ||
                    str[j] == '{')
            {
                if (s.empty())
                {
                    s.push(str[j]);
                }
                else{
                 
                if (ad[str[j]] <= ad[s.top()])
                {
                    s.push(str[j]);
                }
                else
                {
                    printf("NO\n");b=1;break;
                }}
            }
        }
        if (!b)
        {
         
        if (s.empty())
            printf("YES\n");
        else
            printf("NO\n");}
        clear();
    }
 
}

核心思想：
读入数字，则直接输出；
读入 ‘(’ ，入栈；
读入 ‘)’ ，持续输出 + 弹栈，直至栈顶为 ‘(’ ，再次弹栈，结束；
读入运算符，则持续输出 + 弹栈，直至出现第一个运算优先级 < 当前运算符优先级的。
这里 +、- 的优先级为 1；* 、 / 的优先级为 2；( 、 ) ；的优先级为 0。

#include <cstdio>
#include <string>
#include <stack>
#include <iostream>
 
using namespace std;
 
int cmp(char opt)
{
    if ('+' == opt || '-' == opt)   return 1;
    else if ('*' == opt || '/' == opt)  return 2;
    return 0;
}
 
int i;
string str;
stack<char> s;
int main()
{
     
    cin >> str;
    str = " " + str;
    for (i = 1; i < str.length(); ++i)
    {
        if (str[i] >= '0' && str[i] <= '9')
        {
            printf("%c ", str[i]);
        }
        else if (str[i] == '(')
        {
            s.push('(');
        }
        else if (str[i] == ')')
        {
            while (s.top() != '(')
            {
                printf("%c ", s.top());
                s.pop();
            }
            s.pop();
        }
        else
        {
            while (!s.empty() && cmp(s.top()) >= cmp(str[i]))
            {
                printf("%c ", s.top());
                s.pop();
            }
            s.push(str[i]);
        }
    }
    while (!s.empty())
    {
        printf("%c ", s.top());
        s.pop();
    }
     
    return 0;
}

很简单了

#include<cstdio>
#include<cstring>
using namespace std;
int s[1001];
char str[256];
int len,t;
int calc()
{
    for(int i=0;i<len-1;i++)
    {
        switch(str[i])
        {
            case' ':break;
            case'+':s[--t]+=s[t+1];break;
            case'-':s[--t]-=s[t+1];break;
            case'*':s[--t]*=s[t+1];break;
            case'/':s[--t]/=s[t+1];break;
            default:
                int x=0;
                while(str[i]!=' ')
                    x=x*10+str[i++]-'0';
                s[++t]=x;
                break;
        }
    }
    return s[t];
}
int main()
{
    gets(str);
    len=strlen(str);
    printf("%d",calc());
    return 0;
}

作者：Rotch
日期：2020-11-10
修改：2020-11-10