問題タブ [infix-notation]

すでにSOにこれと同様の質問があることは知っていますが、私が抱えている問題を解決する質問を見つけることができません。正しい出力を得るために演算子の優先順位を実装しながら、中置記法式を後置記法に変換するメソッドを作成しようとしています。私は通常のメソッド（push、pop、peekなど）を使用して独自のスタッククラスを作成しましたが、これは完全に正常に機能します。私の問題は、A-（B + C ^ D ^ C）/ D * Bなどのより複雑な式の場合、間違った出力が得られることです。変換の結果はABCDC^^+ D / B *-になるはずですが、私はABCDC ^^ + D/-Bを取得し続けます

これが私の方法です：

コンポーネントメソッドのいずれかが必要な場合はお知らせください。どんな助けでも大歓迎です！

オペランド スタックと演算子スタックを使用して中置記法から前置記法に変換する Java プログラムの作成に取り組んでいます。ここの一番上の回答の疑似コードに基づいて、機能するコンバーターを実装しました。

接頭辞から接頭辞への変換

ただし、現在、上記のアルゴリズムの時間と空間の複雑さを解決しようとしています。

スペースの複雑さは O(n) でなければならないと思います。なぜなら、それらの間で共有される入力を格納する 2 つのスタックしかないからです。

時間の複雑さについて考えると、完全にはわかりませんが、各サブパートをインフィックスからプレフィックスに変換する必要があるため、O(n^2) ですか? この部分についてはよくわかりません。

基本的に私の質問は次のとおりです:私の空間複雑度の結果は正しいですか?アルゴリズムの時間複雑度はどれくらいですか?

どうもありがとう！

編集: これはアルゴリズムの擬似コードです:

これは、単純なネストされた式の基本構造です...

これらの式のリストを作成したい場合は、次を使用できます...

ここでは区切り文字として「,」を使用します。

区切り記号なしで式のリストを作成できるようにしたい。

したがって、文字列があれば、それを次の4 5 2+3 1 6ように解釈できるようにしたいと思います(4) (5) ^(+ 2 3) (1) (6)

問題は、両方が同じ最初のシンボル (INT)4を2+3持っているため、競合が発生することです。私はこれをどのように解決できるかを理解しようとしています。

編集

特定の条件に対して正しい書き換えを思いつくのに苦労しているだけで、ほとんど理解できました...

これは、私が欲しいものです1+2+3++4+5+。^(+ ^(+ 1 2) 3) (+) (+) ^(+ 4 5) (+)

++1+2として解析されるように、書き換えルールを完成させようとしてい(+) (+) ^(+ 1 2)ます。全体として、トークンのリストが必要で、すべての中置式を見つけて、残りをリストとして残します。

接頭辞計算クラスのエラーを特定しようとしていますが、うまくいきません。

予想される出力は次のようになります: InFix: "2+4" (例) PostFix: "24+" PreFix: " 24" (ここにエラーがあります)

プレフィックスを計算するクラスは次のとおりです。

私のコードを改善する方法やこのエラーを修正する方法について誰かが提案を持っている場合は、大歓迎です!

事前にt​​hx。

今日は本を読みました。infix から postfix への変更に関するアルゴリズムが導入されました。利点とは? 前もって感謝します。

I want to know if there is a way to solve infix expressions in a single pass using 2 stacks? The stacks can be one for operator and the other for operands...

The standard way to solve by shunt-yard algorithm is to convert the infix expression to postfix(reverse polish) and then solve. I don't want to convert the expression first to postfix.

If the expression is like 2*3-(6+5)+8, how to solve?

私はJavaScriptの初心者です。

このコードは、接尾辞式を評価することになっています。しかし、それは機能しません。コードは非常に論理的で、何が問題なのかよくわかりません。

誰かが私を助けてくれるなら、私は感謝するでしょう！

C中置式を後置に変換し、入力した値で計算するプログラムを作成しようとしています。（2 + 14）* 5と入力すると、（2 14）5 * +になりますが、2 14 +5*になります。だから私の質問：

1. どこで私は間違えましたか？
2. 最後のフォーム（接尾辞）の括弧を削除するようにコードを変更するにはどうすればよいですか？

助けてくれてありがとう。

1週間前に始めた小さな中置計算機が完成する頃だと判断し、評価関数で問題が発生しました。私のswitchステートメントには、演算子構造体での配列の処理方法に問題があるようです。何が間違っているのか完全にはわかりません。私が受けているエラーはこれだけではありませんが、これを修正すれば、他の問題をより簡単に解決できるはずです。明らかに私のコードは不完全ですが、これまでのところ、私は正しい方向に進んでいますか？