BOJ 1918-接尾辞式

タイムアウトメモリ制限正解の送信正解正解正解正解率2秒128 MB 14892758342831.706%

質問する

修飾は一般的に3つのマーキング法で表現することができる.演算子は被演算子の中間に位置する中位数表現(通常は我々が使用する方法)、演算子は被演算子の前に位置するプレフィックス表現(prefix表現)、演算子は被演算子の後ろに位置する接尾辞表現(postfix表現).例えば、中位マーキング法で表されるa+b、電位マーキング法で表されるa+ab、後位マーキング法で表されるa+bである.
この問題では,我々が処理するマーキング法は接尾辞マーキング法である.接尾辞表現は、前述したように、被演算子の後ろに演算子を置く方法である.この方法の利点は次のとおりです.我々がよく用いる中位数タグ式では,加算と乗算の優先度に差があるため左から右へ順次計算することはできないが,接尾辞タグ式を用いて順序を適切に調整して順序を決定することができる.また、同じ方法でも括弧などは必要ありません.たとえば、a+b*cを接尾辞タグに変換するとabc*+になります.
中尉表記式を後尉表記式に変更する方法を簡単に説明します.まず、演算子の優先度に応じて、与えられた中位タグをカッコで囲みます.次に、カッコ内の演算子をカッコの右側に移動します.
たとえば、a+b*cは(a+(b*c))の式と同じになります.次に、カッコ内の演算子*をカッコ外から取り出します(a+bc*).最後に、+を括弧の右側、すなわちabc*+に変更します.
例えば、A+B*C-D/Eを完全に括弧で囲み、演算子を移動する場所を図で示すと、以下のようになります.

これらの事実を知った上で、中尉マーク式を与える場合は、後列マーク式修正プログラムを作成してください.

入力

最初の行には、中位タグ式が表示されます.しかしこの式の被演算子はA~Zの文字で構成されており,式には一度しか現れない.また、A+B-の前面やAB省略*などの修飾は与えられない.記号は、アルファベット+、-、*、/、(、)のみで構成され、長さは100を超えません.

しゅつりょく

1行目に改行を印刷してください

に近づく

この問題はもともとStackで解くことを知っていた.
かっこの場合、文字の場合、修飾時にどのように展開するかを考えるだけです.

文字の場合:文字の順序が同じなので、正解文字列にそのまま入れればいいです.

かっこ"(":スタック.

)

カッコ""の場合:"(1つに遭遇するまで)、スタックから削除して正解文字列を入れます.

"*"、"/"の場合:スタックに"+"、"-"がある場合は、それを減算して正解文字列に入れます.

"+"、"-"の場合:"(")が"に遭遇するまでスタックから正解文字列を取り出して入れます.

に答える

上記とほぼ同じです.
文字列を迂回して、stackに残りの値を入れるだけです.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

string str, ans = "";
stack<char> S;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN(str);
	for (char ch : str)
	{
		if ('A' <= ch && ch <= 'Z') ans += ch;
		else if (ch == '(')
		{
			S.push(ch);
		}
		else if (ch == ')')
		{
			while (!S.empty() && S.top() != '(')
			{
				ans += S.top();
				S.pop();
			}
			S.pop();
		}
		else if (ch == '*' || ch == '/')
		{
			while (!S.empty() && (S.top() == '*' || S.top() == '/'))
			{
				ans += S.top();
				S.pop();
			}
			S.push(ch);
		}
		else
		{
			while (!S.empty() && S.top() != '(')
			{
				ans += S.top();
				S.pop();
			}
			S.push(ch);
		}
	}
	while (!S.empty())
	{
		ans += S.top();
		S.pop();
	}

	COUT(ans);

	return 0;
}