中置式（など）を後置式（など）に変換するために使用できる有名な操車場アルゴリズムがあります。操車場アルゴリズムには、移動しようとしている要素を格納するためのスタックが必要です。1 + 2 * 31 2 2 * +
線形時間と一定のメモリで特定の入力を接尾辞形式に変換するために必要なスタックの長さを事前に見積もることは可能ですか？
質問する
167 次
2 に答える
3
もちろん。操車場アルゴリズムは、演算子（括弧を含む）のみをスタックにプッシュするため、1次近似は式内の演算子の数です。もう少しインテリジェンスがあれば、表現をスキャンして、関連性とグループ化を探すことができます。しかし、完了するまでに、式に必要なスタックサイズの最適な見積もりを決定するためのスタックベースのアルゴリズムを作成し、実行コストを2倍にしたはずです。
于 2013-03-12T21:41:14.160 に答える
0
古いHP-45計算機では、常に最も深くネストされた括弧をスキャンし、そこで評価を開始しました。これは、入力内のN個のトークンに対するクイックO（N）アルゴリズムである必要があります。
実際には、HP-45の4つの高さのスタックを吹き飛ばす表現を作成することは困難でした。
于 2013-03-12T21:52:42.647 に答える