算術式の文字列を指定すると、式の小数値が見つかります。

Question

インタビュー質問です。

算術式の文字列を指定すると、式の小数点の値が見つかります。

例：与えられた

30*(5+10) is a string, its value is 450. 

私の考え：

解析各シンボル1つずつの演算子の優先順位を持つ表現として文字列を再構築します。しかし、それは効率的ではありません、それはO（n^2）かそれ以上です。

もっと良いアイデア？

おかげ

Answer 1

あなたはO（n）の時間でのスタックを使用して接尾辞に式を変換することができます。

次に、O（n）回のスタックで後置式を評価します。

式の評価中に演算子の優先順位を決定するには、Postfixに変換する必要があります。

http://www.cs.wcupa.edu/~rkline/DS/deque-stack-algorithms.html

Answer 2

解析スタックと演算式の評価を参照して、有限状態オートマトンで文字列をトークン化：

整数 - >整数トークン

オペレータ - >トークン演算子

開始ブラケット - >状態 - 新しい式

閉じるブラケット - >状態 - クローズexpr ession

あなたはツリーを構築し、ツリーボトムアップを平らにすることで実行できます。

Answer 3

貿易の条件についての操作を記述する：算術式のパーサーを構築または見つける、文字列を解析し、抽象構文木（AST）を評価して結果を返す。算術式は文脈自由言語であり、LL(1)にあるので、これはO(n)で可能です。パーサーの構築は、Boost.Spiritやyaccで安価です。

Answer 4

前に付加C中括弧の余分なペアに包まれた式の前の文字列"print "、末尾にセミコロンを入れて、-eのperlに渡し、すなわち：

system("perl -e 'print (30*(5+10));'");