c++スタックの応用初歩

4つの「スタックの応用」を整理しました
Q 1:(入門)問題A:プログラマー入力問題時間制限:1 Secメモリ制限:128 MB題目説明【問題説明】プログラマー入力プログラムにエラーが発生した場合、次の救済措置をとることができる:1つのキーを押し間違えた場合、前の文字が無効であることを表すために1つの退格符「#」を押すことができる;現在の1行のエラーを発見した場合、1つの退行符「@」を押すことができる「@」と前の改行文字の間の文字がすべて無効であることを示します.【入力形式】1行の文字を入力し、個数は100を超えない.【出力形式】1行の文字を出力し、実際の有効文字を表す.【入力サンプル】sdfosif@for(ii#=1,#;i<.>【出力サンプル】for(i=1;i<=8;i+);
直接コード:

#include 
using namespace std;
int main()
{
    char s[101];
    stack <char> a;
    stack <char> b;
    gets(s);
    for(int i=0;i<strlen(s);i++)
	{
        if(s[i]=='@')
		{
            while(!a.empty())
			{
                a.pop();
            }
            continue;
        }
        if(s[i]=='#')
		{
            if(!a.empty())
			{
                a.pop();
                continue;
            }
        }
        a.push(s[i]);
    }
    while(!a.empty())
	{
        b.push(a.top());
        a.pop();
    }
    while(!b.empty())
	{
        cout<<b.top();
        b.pop();
    }
    cout<<endl;
    return 0;
}

AC W 2:この問題はちょっと面倒な問題です.B:溶液シミュレータ時間制限:1 Secメモリ制限:128 MBテーマ説明謝さんは溶液がたくさんありますが、ほしい溶液に合うことができません.万が一間違えたら取り返しがつかないからです.そこで、謝さんはネット上で溶液配置シミュレータをダウンロードしました.シミュレータはコンピュータに仮想溶液を構築し、現在の仮想溶液に一定濃度、一定体積のこの溶液を仮想的に加えることができ、シミュレータは注入後の仮想溶液の濃度と体積を迅速に算出する.もちろん、間違えたら取り消すことができます.シミュレータの使用手順は以下の通りである:1)シミュレータの初期体積と濃度V 0,C 0%を設定する.2)一連の操作を行い、シミュレータは2つの操作をサポートする:P(v,c)操作:現在の仮想溶液に体積v濃度cの溶液を加えることを示す;Z操作:前ステップのP操作を取り消します.1行目の2つの整数を入力し、V 0とC 0、0≦C 0≦100を表す.2行目の整数nは、操作数を表し、n≦10000である.次のn行は、行ごとに1つの操作で、フォーマットは:P_v_cまたはZ.そのうち_スペースを表し、初期溶液しか残っていない場合は取り消しても無駄です.任意の時点で質量は2^31-1を超えない.出力n行目、各行2個数Vi,Ci、Viが整数、Ciが実数(小数5桁保持)である.ここで、i行目はi回目以降の溶液体積と濃度を示す.サンプル入力Copy 100 2 P 100 0 Z
ちょっと考えればよかった:

#include 
using namespace std;
struct ry
{
    int v;
    double c;
};
stack<ry>vis;
int main()
{
    ios::sync_with_stdio(0);
    char p;
    int v0,v1,v2,n;
    double c0,c1,c2;
    cin>>v0>>c0>>n;
    v2=v0;
    c2=c0;
    for(int i=0;i<n;i++)
	{
        cin>>p;
        if(p=='P')
		{
            cin>>v1>>c1;
            vis.push({v1,c1});
            c0=(v0*c0+v1*c1)/(v0+v1);
            c0=c0;
            v0=v0+v1;
            printf("%d %.5lf
",v0,c0);
        }
        else
		{
            if(vis.empty())
			{
                printf("%d %.5lf
",v2,c2);
                continue;
            }
            ry tmp=vis.top();
            vis.pop();
            v1=tmp.v;
            c1=tmp.c;
            c0=(v0*c0-v1*c1)/(v0-v1);
            v0=v0-v1;
            printf("%d %.5lf
",v0,c0);
        }
    }
    return 0;
}

この問題も一度に合格した.W 3:問題C:式括弧マッチング時間制限:1 Secメモリ制限:128 MB題目記述1つの式が英字(小文字)と数字、演算子(+、—、/)と左右(円)括弧で構成されていると仮定するを選択します.式の左右の括弧が一致しているかどうかを確認するプログラムを作成してください.一致したら「YES」を返します.そうでなければ「NO」を返します.式の長さは255未満で、左カッコは20未満です.入力入力ファイルには、1行のデータ、すなわち式が含まれ、出力ファイルには1行、すなわち「YES」または「NO」が含まれる.サンプル入力Copy 2(x+y)/(1-x)@サンプル出力Copy YES
私のこの問題は5回やっとACを渡して、前の4回はすべてメモリが期限を超えました:間違い:

#include 
using namespace std;
int main()
{
    char s[300];
    stack <char> a;
    scanf("%s",s);
    for(int i=0;i<strlen(s);i++)
	{
        if(a.empty()) a.push(s[i]);
        else
		{
            if(a.top()=='['&&s[i]==']'||a.top()=='('&&s[i]==')')
                a.pop();
            else
                a.push(s[i]);
        }
    }
    if(a.empty()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

メモリ超過
ACの正しいバージョン:

#include
using namespace std;
#define N 260
int main()
{
char s[N];
int top=0,i=0;
scanf("%s",s);
while(s[i]!='@')
{
    if(s[i]=='(')
           top++;
    if(s[i]==')')
    {
        if(top>0) top--;
        else
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    i++;
}

if(top!=0)  
cout<<"NO"<<endl;
else 
cout<<"YES"<<endl;
  return 0;
}

みんなやってみよう!Q 4:問題D:式評価時間制限:1 Secメモリ制限:512 MBコミット:43解決:16[状態][コミット][命題者:外部インポート]問題説明加算と乗算のみを含む算術式を指定し、式の値をプログラミングしてください.入力は1行のみで、計算が必要な式のために入力されます.式には、数値、加算演算子「+」、乗算演算子「*」のみが含まれ、カッコはなく、演算に参加するすべての数値は0から2^31-1の整数です.入力データは、この行に0~9、+、*の12文字しかないことを保証します.
【データ範囲】30%のデータに対して、0≦式の加算演算子と乗算演算子の総数≦100;80%のデータに対して、0≦式の加算演算子と乗算演算子の総数≦1000;100%のデータに対して、0≦式の加算演算子と乗算演算子の総数≦100000.
出力出力は1行のみで、この式の値を表す整数が含まれています.注意:答えの長さが4ビット以上の場合は、最後の4ビットのみ出力し、先頭0は出力しません.サンプル入力Copy 1+1*3+4サンプル出力Copy 8
みんなはまず問題を解く方法を考えてからcopyに行きます.これはACバージョンです.

#include 

using namespace std;

int main()
{
    stack <int>a;
    int t,s=0;
    char ch='+';
    while(ch=='+'||ch=='*')
    {
        cin >> t ;
        t=t%10000;
        if(ch=='+')
            a.push(t);
        else if(ch=='*')
        {
            t=(a.top()*t)%10000;
            a.pop();
            a.push(t);
        }
        ch=getchar();
    }
    while(!a.empty())
    {
        s=(s+a.top())%10000;
        a.pop();
    }
    cout<<s<<endl;
    return 0;
}

今、皆さん、次のような間違いを見てください.ありがとうございます.

#include 
using namespace std;
const int mod=1e4;
char c;
int x,sum,ans;
int main()
{
    scanf("%d",&x);sum=x%mod;
    while(scanf("%c",&c)&&c!='
')
    {
        scanf("%d",&x);
        x=x%mod;
        if(c=='*')
            sum=sum*x%mod;
        else 
		{
            ans=ans+sum%mod;
            sum=x%mod;
        }
    }
    ans=ans+sum%mod;
    printf("%d
",sum%mod);
    return 0;
}

よし、これだけだから、早く手の練習に行きましょう.