3

中置電卓の文法で式を解析して評価するにはどうすればよいですか?私は2つの方法を考えました。

1つ目は、2つのスタックを使用することです。1つは数値用で、もう1つは演算子用です。式の評価方法を理解するために、演算子の優先順位と関連付けを評価します。

2番目の方法では、中置式を後置に変換しますが、これをどのように実行すればよいかわかりません。それはただのアイデアでした。現在、私は最初の方法を使用することを意図してプログラムを設定しました。

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

bool die(const string &msg);

//stack class
class Stack{
public:
    Stack();
    void push(const double &val);
    void push(const string &oper);
    double popnum();
    string popop();
    double getopele();
    double getnumele();
private:
    static const unsigned MAX=30;
    string opstack[MAX];
    double numstack[MAX];
    unsigned opele;
    unsigned numele;
};

//operator type
struct OP{
    string name;
    void * func;
    unsigned arity;
    unsigned prec;
    bool lass;
    string descrip;
};
//operator table
OP op[]={{"+", add, 2, 4, true, "2+3 is 5"},
        {"-", subtract, 2, 4, true, "2-3 is -1"},
        {"*", multiply, 2, 6, true, "2*3 is 6"},
        {"/", divide, 2, 6, true, "2/3 is 0.666666..., div by 0 illegal"}};
unsigned OPELE =sizeof(op)/sizeof(op[0]);

//operators
bool add(double &r, double &x, double &y);
bool subtract(double &r, double &x, double &y);
bool multiply(double &r, double &x, double &y);
bool divide(double &r, double &x, double &y);

//Manip
unsigned findindex(string token, OP op[], unsigned OPELE);
bool parse(double &t, const string &token);
bool evaluate(double &result, string line);
bool weird(double x);

int main(){
    for(string line; getline(cin, line);){
        if(line=="QUIT") break;
        if(line.empty()) continue;
        if(line=="DOC")
            for(unsigned i=0; i<OPELE; i++)
                cout<<op[i].name<<" | "<<op[i].descrip<<'\n';
        double result;
        if(evaluate(result, line)){
            cout<<result<<'\n';
        }else{
            cout<<"Could not understand input\n\n";
        }
    }
}

Stack::Stack(){
    opele=0;
    numele=0;
}

void Stack::push(const double &val){
    if(MAX) die("Stack Overflow");
    numstack[numele++]=val;
}

void Stack::push(const string &oper){
    if(MAX) die("Stack Overflow");
    opstack[opele++]=oper;
}

double Stack::popnum(){
    if(!numele) die("Stack Underflow");
    return numstack[--numele];
}

string Stack::popop(){
    if(!opele) die("Stack Underflow");
    return opstack[--opele];
}

double Stack::getopele(){
    return opele;
}

double Stack::getnumele(){
    return numele;
}

bool add(double &r, double &x, double &y){
    double t = x + y;
    if( weird(t) )  return false;
    r = t;
    return true;
}

bool subtract(double &r, double &x, double &y){
    double t = x - y;
    if( weird(t) )  return false;
    result = t;
    return true;
}

bool multiply( double & r, double& x, double &y ){
    double t = x * y;
    if( weird(t) )  return false;
    result = t;
    return true;
}

bool divide( double & result, double &x, double &y ){
    double t = x / y;
    if( weird(t) )  return false;
    result = t;
    return true;
}

unsigned findindex(string token, OP op[], unsigned OPELE){
    for(unsigned i=0l i<OPELE; i++)
        if(op[i].name==token)
            return i;
    return UINT_MAX;

}

bool parse(double &t, const string &token){
    istringstream sin( token );
    double t;
    if( !(sin >>t) )  return false;
    char junk;
    if( sin >>junk )  return false;
    value = t;
    return true;
}

bool evaluate(double &result, string line){
    istringstream sin(line);
    Stack s;
    for(string token; sin>>token;){
        double t;
        if(parse(t, token)){
            s.push(t);
        }else if(
    }
}

bool weird( double x ){
    return  x != x || x != 0 && x == 2*x;
}
4

2 に答える 2

9

これは長い間読まれますが、とにかく、私が中置式を解析してそれを二分木として保存するために使用するアルゴリズムをあなたと共有します。スタックではなく、二分木です。接尾辞の順序を簡単に指定できる構文解析。これが最高のアルゴリズムだとは言いませんが、これは私のスクリプト言語では機能します。

アルゴリズム:

二分木の「現在のノード」と「現在の式」を操作するメソッドがあります。ノードには、「データ」フィールドと「タイプ」フィールドが含まれています。

ステージ1:「4」などの単純なものがノードに直接入り、タイプを「DATA」として指定します。この情報をそのまま使用してください。

ステージ2:では、次の式について考えてみましょう。

a) 2 + 3

これは次の二分木に変換されます。

  +
 / \
2   3

したがって、演算子はノードに入り、オペランドはリーフに入ります。式a)をツリーに変換するのは非常に簡単です。演算子を見つけ、ツリーの「現在の」ノードに配置し、ノードのタイプを演算子「PLUS」に指定すると、残っているものがツリーに入ります。ノードの左側では、ノードの右側が右側のツリーに入ります。素晴らしくシンプルで、ステージ1の情報を使用すると、2つのリーフは値2と3の「DATA」リーフになります。

ステージ3:しかし、より複雑な表現の場合:

b) 2 * 3 + 4

ツリーは次のようになります。

    +
   / \ 4
  *
 / \ 
2   3

したがって、上記のアルゴリズムを次のように変更する必要があります。優先順位が最も高い最初の演算子を見つけます(c++ガイドラインを考慮して...+(プラス)と-(マイナス)の優先順位は6ですが、*(乗算)の優先順位は/(除算)および%(モジュロ)は5)式で、式を2つの部分(優先順位が最も高いオペランドの前と優先順位が最も高いオペランドの後)に分割し、演算子を次のように配置しながら、2つの部分のメソッドを再帰的に呼び出します。現在のノードへの最高の優先順位。したがって、次のようなhdataを使用してツリーを作成します。

    +
   / \ 
  /  call method with "4"
call method with "2*3"

この段階で、呼び出し(「2 * 3」)の場合は「ステージ2」に、呼び出し「4」の場合は「ステージ1」にフォールバックします。

ステージ4:式にparanthesisがある場合はどうなりますか?そのような

c) 2 * (3 + 4)

これにより、ツリーが作成されます。

      *
     / \
    2   +
       / \
      3   4

アルゴリズムを次のように変更します。

  • 現在の式がパランテシスで囲まれている間に、パランテシスを削除してアルゴリズムを再起動します。気をつけて。(2 + 3 * 4 + 5)は、parnethesisで囲まれていると見なされますが、(2 + 3)*(4 + 5)はそうではありません。したがって、それは式の開始文字と終了文字だけではなく、事実上、括弧を数える必要があります。(これは再帰的な方法です。最初のステップを恐れないでください...)
  • ここで、式の括弧の外側で優先順位が最も高い最初の演算子を見つけます。繰り返しますが、式の左側と右側を取り、「ステージ1」に到達するまで、メソッドを何度も呼び出します。単一のデータ要素で。

    これは、単純な数値と演算子で構成される式のアルゴリズムです。より複雑な情報については、ニーズに合わせて情報を調整する必要がある場合があります。価値があると思われる場合は、https://sourceforge.net/p/nap-script/mercurial/ci/default/tree/compiler/interpreter.cppをご覧ください。これには、より複雑な概念(変数、メソッド呼び出し、接尾辞/接頭辞演算子など)に関する上記のアルゴリズムの完全な実装(C)が含まれています。メソッドはbuild_expr_treeで、1327行目から始まります。

于 2012-12-13T09:29:29.003 に答える
4

再帰下降の方法は、正しい式パーサーを手動で実装する最も簡単な方法です。ここで、プログラミング言語スタックは、使用しようとしている明示的なスタックと同じことを行います。グーグルで見つけられる多くのRDの例があります、そして、どんな良いコンパイラ本でもいくつかを持っているでしょう。

リンクされたウィキペディアのページにはパーサーが表示されますが、評価を追加する方法は表示されません。したがって、以下はCの完全な基本式エバリュエーターです。グローバル変数がインスタンス変数になるC++クラスで簡単にラップできます。実動システムに必要な機能が不足しています。たとえば、エラーが見つかった場合は、終了するだけです。C ++の例外を使用すると、再帰を簡単に巻き戻して続行できます。また、数値のオーバーフロー、ゼロ除算などに対する保護も必要です。これは、明らかにその方法を知っています。

再帰下降の考え方は、目的の言語の文法をLL(1)と呼ばれる形式に変換することです。それが完了すると、文法規則をプロシージャに変換するための固定規則(毎回機能することが保証されています)があります。私はこれを以下で手作業で行いました。それを自動的に行うためのツールがあります。

したがって、この評価者は非常に簡単に拡張できます。必要な文法規則を追加してから、スキャナー、パーサー、および評価コードに必要な拡張機能を実装するだけです。たとえば、組み込みの関数ルールは次のようになりますunsigned_factor -> FUNCTION_NAME ( expr )。この場合、スキャナーはすべての関数名を同じトークンとして認識し、unsigned_factorC関数は値を解析および計算するために拡張されます。

プログラムを動作させるには、小さなスキャナーを含める必要がありました。コードの半分以上がスキャナーであることに注意してください。基本的なRDパーサーは単純です。

エラー回復を追加すると、より複雑になります。エラーをスキップして解析を続行し、正確に表現されたエラーメッセージを1つだけ出力するインテリジェントな機能です。しかし、繰り返しになりますが、これにより、パーサーに多くの複雑さが加わります。

// Bare bones scanner and parser for the following LL(1) grammar:
// expr -> term { [+-] term }     ; An expression is terms separated by add ops.
// term -> factor { [*/] factor } ; A term is factors separated by mul ops.
// factor -> unsigned_factor      ; A signed factor is a factor, 
//         | - unsigned_factor    ;   possibly with leading minus sign
// unsigned_factor -> ( expr )    ; An unsigned factor is a parenthesized expression 
//         | NUMBER               ;   or a number
//
// The parser returns the floating point value of the expression.

#include <stdio.h>
#include <stdlib.h>

// The token buffer. We never check for overflow! Do so in production code.
char buf[1024];
int n = 0;

// The current character.
int ch;

// The look-ahead token.  This is the 1 in LL(1).
enum { ADD_OP, MUL_OP, LEFT_PAREN, RIGHT_PAREN, NUMBER, END_INPUT } look_ahead;

// Forward declarations.
void init(void);
void advance(void);
double expr(void);
void error(char *msg);

// Parse expressions, one per line. 
int main(void)
{
  init();
  while (1) {
    double val = expr();
    printf("val: %f\n", val);
    if (look_ahead != END_INPUT) error("junk after expression");
    advance();  // past end of input mark
  }
  return 0;
}    

// Just die on any error.
void error(char *msg)
{
  fprintf(stderr, "Error: %s. I quit.\n", msg);
  exit(1);
}

// Buffer the current character and read a new one.
void read()
{
  buf[n++] = ch;
  buf[n] = '\0';  // Terminate the string.
  ch = getchar();
}

// Ignore the current character.
void ignore()
{
  ch = getchar();
}

// Reset the token buffer.
void reset()
{
  n = 0;
  buf[0] = '\0';
}

// The scanner.  A tiny deterministic finite automaton.
int scan()
{
  reset();
START:
  switch (ch) {
    case ' ': case '\t': case '\r':
      ignore();
      goto START;

    case '-': case '+':
      read();
      return ADD_OP;

    case '*': case '/':
      read();
      return MUL_OP;

    case '(':
      read();
      return LEFT_PAREN;

    case ')':
      read();
      return RIGHT_PAREN;

    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
      read();
      goto IN_LEADING_DIGITS;

    case '\n':
      ch = ' ';    // delayed ignore()
      return END_INPUT;

    default:
      error("bad character");
  }

IN_LEADING_DIGITS:
  switch (ch) {
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
      read();
      goto IN_LEADING_DIGITS;

    case '.':
      read();
      goto IN_TRAILING_DIGITS;

    default:
      return NUMBER;
  }

IN_TRAILING_DIGITS:
  switch (ch) {
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
      read();
      goto IN_TRAILING_DIGITS;

    default:
      return NUMBER;
  }          
}

// To advance is just to replace the look-ahead.
void advance()
{
  look_ahead = scan();
}

// Clear the token buffer and read the first look-ahead.
void init()
{
  reset();
  ignore(); // junk current character
  advance();
}

double unsigned_factor()
{
  double rtn = 0;
  switch (look_ahead) {
    case NUMBER:
      sscanf(buf, "%lf", &rtn);
      advance();
      break;

    case LEFT_PAREN:
      advance();
      rtn = expr();
      if (look_ahead != RIGHT_PAREN) error("missing ')'");
      advance();
      break;

    default:
      error("unexpected token");
  }
  return rtn;
}

double factor()
{
  double rtn = 0;
  // If there is a leading minus...
  if (look_ahead == ADD_OP && buf[0] == '-') {
    advance();
    rtn = -unsigned_factor();
  }
  else
    rtn = unsigned_factor();
  return rtn;
}

double term()
{
  double rtn = factor();
  while (look_ahead == MUL_OP) {
    switch(buf[0]) {
      case '*':
        advance(); 
        rtn *= factor(); 
        break; 

      case '/':
        advance();
        rtn /= factor();
        break;
    }
  }
  return rtn;
}

double expr()
{
  double rtn = term();
  while (look_ahead == ADD_OP) {
    switch(buf[0]) {
      case '+': 
        advance();
        rtn += term(); 
        break; 

      case '-':
        advance();
        rtn -= term();
        break;
    }
  }
  return rtn;
}

そしてプログラムを実行する:

1 + 2 * 3
val: 7.000000
(1 + 2) * 3
val: 9.000000
于 2012-12-15T19:00:00.857 に答える