🆓 👩🏿‍🚀 🚡 再帰降下法を使用したパーサーの式 🎚️ ✊🏻 💻

親愛なるハブロフチアン！

Java言語の変数と関数をサポートする数式のサンプルパーサーを作成して、「再帰降下法」アルゴリズムの実装を共有したい

（ほとんどの場合、私は:)）のこの記事が初心者にとって興味深いものになるか、この問題の解決策の基礎として使用してください。

誰が気にする-カットをお願いします

TK

次の式のパーサーを開発します。

正しい操作キューに準拠
機能をサポート
変数をサポート

エントリー

このメソッドの本質は、サブタスクに分割されることです。順番に、サブタスクは、それが機能できるものでのみ機能する必要があり、条件が満たされない場合、制御をさらに転送します。条件が満たされた場合、計算を行い、残りの生のテキストを転送します。テキストがまだある限り、または現在の状態を処理できるサブタスクがない場合、実行が行われます。

サブタスクの優先度も重要です。サブタスクの優先度を変更すると、パーサーの動作が変更されます。

数式のパーサーを実装するため、優先順位付けのために、数学演算の優先順位がガイドされます。

関数と変数
括弧
乗算と除算
足し算と引き算

飛んだ

さて、ここまでです。

上で述べたように、残りの行を操作します。つまり、各タスクは歯の中にあるものを噛み、飲み込むことができないことを伝えます。

合計では、次の構造が必要です。

文字列の残りを保持する文字列変数

計算プロセスの現在の状態を保存するためのいわゆるバッテリー

必要ですか？やりましょう！

class Result { public double acc; public String rest; public Result(double v, String r) { this.acc = v; this.rest = r; } }

パーサー自体から始めましょう。

最初に呼び出すものは、優先度が最も低いサブタスクです。

次に、サブタスクは優先度の高いサブタスクの制御を転送し、テキストに影響を与えた各アクションの後に、優先度の高いサブタスクの制御も転送します。

そして、前述のように、プログラムは解析するものが見つかるまで、またはデータの未知の構造またはシーケンスにつまずくまで続きます。

加算/減算を実行する方法から、乗算/除算などを引き起こします

一般的な理解のために、タスクを少し単純化し、加算と減算の演算のみを実行するパーサーを作成しましょう。

 public class MatchParserPlusMinus { public MatchParserPlusMinus(){} public double Parse(String s) throws Exception { Result result = PlusMinus(s); if (!result.rest.isEmpty()) { System.err.println("Error: can't full parse"); System.err.println("rest: " + result.rest); } return result.acc; } private Result PlusMinus(String s) throws Exception { Result current = Num(s); double acc = current.acc; while (current.rest.length() > 0) { if (!(current.rest.charAt(0) == '+' || current.rest.charAt(0) == '-')) break; char sign = current.rest.charAt(0); String next = current.rest.substring(1); acc = current.acc; current = Num(next); if (sign == '+') { acc += current.acc; } else { acc -= current.acc; } current.acc = acc; } return new Result(current.acc, current.rest); } private Result Num(String s) throws Exception { int i = 0; int dot_cnt = 0; boolean negative = false; //       if( s.charAt(0) == '-' ){ negative = true; s = s.substring( 1 ); } //      while (i < s.length() && (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) { //   ,        ! if (s.charAt(i) == '.' && ++dot_cnt > 1) { throw new Exception("not valid number '" + s.substring(0, i + 1) + "'"); } i++; } if( i == 0 ){ // -       throw new Exception( "can't get valid number in '" + s + "'" ); } double dPart = Double.parseDouble(s.substring(0, i)); if( negative ) dPart = -dPart; String restPart = s.substring(i); return new Result(dPart, restPart); } }

呼び出し時：

  MatchParserPlusMinus pm = new MatchParserPlusMinus(); String f = "10-8+2+6"; try{ System.out.println( "PlusMinus: " + pm.Parse(f) ); }catch(Exception e){ System.err.println( "Error while parsing '"+f+"' with message: " + e.getMessage() ); }

私たちに出力されます：

PlusMinus: 10.0

このパーサーでは、次の関数を実装しました（対応する条件をprocessFunctionに追加することにより、関数でこのリストを展開できます）。

罪
cos
日焼け

エラー処理は特に気にしませんでした（「有用な」コードが乱雑にならないように）。そうしないと、結果として、エラー処理コードがパーサー自体のコードよりも大きくなる可能性があります。

以下に、単純化せずにクラスの完全なリストを示します。

 public class MatchParser { private HashMap<String, Double> variables; public MatchParser() { variables = new HashMap<String, Double>(); } public void setVariable(String variableName, Double variableValue) { variables.put(variableName, variableValue); } public Double getVariable(String variableName) { if (!variables.containsKey(variableName)) { System.err.println( "Error: Try get unexists variable '"+variableName+"'" ); return 0.0; } return variables.get(variableName); } public double Parse(String s) throws Exception { Result result = PlusMinus(s); if (!result.rest.isEmpty()) { System.err.println("Error: can't full parse"); System.err.println("rest: " + result.rest); } return result.acc; } private Result PlusMinus(String s) throws Exception { Result current = MulDiv(s); double acc = current.acc; while (current.rest.length() > 0) { if (!(current.rest.charAt(0) == '+' || current.rest.charAt(0) == '-')) break; char sign = current.rest.charAt(0); String next = current.rest.substring(1); current = MulDiv(next); if (sign == '+') { acc += current.acc; } else { acc -= current.acc; } } return new Result(acc, current.rest); } private Result Bracket(String s) throws Exception { char zeroChar = s.charAt(0); if (zeroChar == '(') { Result r = PlusMinus(s.substring(1)); if (!r.rest.isEmpty() && r.rest.charAt(0) == ')') { r.rest = r.rest.substring(1); } else { System.err.println("Error: not close bracket"); } return r; } return FunctionVariable(s); } private Result FunctionVariable(String s) throws Exception { String f = ""; int i = 0; //      //       while (i < s.length() && (Character.isLetter(s.charAt(i)) || ( Character.isDigit(s.charAt(i)) && i > 0 ) )) { f += s.charAt(i); i++; } if (!f.isEmpty()) { //  -  if ( s.length() > i && s.charAt( i ) == '(') { //      -   Result r = Bracket(s.substring(f.length())); return processFunction(f, r); } else { //  -   return new Result(getVariable(f), s.substring(f.length())); } } return Num(s); } private Result MulDiv(String s) throws Exception { Result current = Bracket(s); double acc = current.acc; while (true) { if (current.rest.length() == 0) { return current; } char sign = current.rest.charAt(0); if ((sign != '*' && sign != '/')) return current; String next = current.rest.substring(1); Result right = Bracket(next); if (sign == '*') { acc *= right.acc; } else { acc /= right.acc; } current = new Result(acc, right.rest); } } private Result Num(String s) throws Exception { int i = 0; int dot_cnt = 0; boolean negative = false; //       if( s.charAt(0) == '-' ){ negative = true; s = s.substring( 1 ); } //      while (i < s.length() && (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) { //   ,        ! if (s.charAt(i) == '.' && ++dot_cnt > 1) { throw new Exception("not valid number '" + s.substring(0, i + 1) + "'"); } i++; } if( i == 0 ){ // -       throw new Exception( "can't get valid number in '" + s + "'" ); } double dPart = Double.parseDouble(s.substring(0, i)); if( negative ) dPart = -dPart; String restPart = s.substring(i); return new Result(dPart, restPart); } //     ,       private Result processFunction(String func, Result r) { if (func.equals("sin")) { return new Result(Math.sin(Math.toRadians(r.acc)), r.rest); } else if (func.equals("cos")) { return new Result(Math.cos(Math.toRadians(r.acc)), r.rest); } else if (func.equals("tan")) { return new Result(Math.tan(Math.toRadians(r.acc)), r.rest); } else { System.err.println("function '" + func + "' is not defined"); } return r; } }

そして呼び出されたとき：

  String[] formulas = new String[] { "2+2*2", "2+X*2", "sin(90)+4-cos(0)", "2--4", "2**3*5-----7", "3.5.6-2" }; MatchParser p = new MatchParser(); p.setVariable("X", 2.0 ); for( int i = 0; i < formulas.length; i++){ try{ System.out.println( formulas[i] + "=" + p.Parse( formulas[i] ) ); }catch(Exception e){ System.err.println( "Error while parsing '"+formulas[i]+"' with message: " + e.getMessage() ); } }

出力されます：

2+2*2=6.0 
      

        
        
        
      

     2+X*2=6.0 
      

        
        
        
      

     sin(90)+4-cos(0)=4.0 
      

        
        
        
      

     2--4=6.0 
      

        
        
        
      

     Error while parsing '2**3*5-----7' with message: can't get valid number in '*3*5-----7' 
      

        
        
        
      

     Error while parsing '3.5.6-2' with message: not valid number '3.5.'

ここからプロジェクト全体をダウンロードできます（アーカイブを保存できるヒントについてはflexoidに感謝します）

ご清聴ありがとうございました！

再帰降下法を使用したパーサーの式

TK

エントリー

飛んだ

More articles: