0

ポーランド記法で式を評価するための再帰的な解決策を探していましたが、見つかりませんでしたが、そのための擬似コードを見つけて、C++に変換したかったのですが難しいです。やり方がわからないところにBIGLETTERSを書きました。私を訂正してください。私はjavaの人で、私にとってC ++は大混乱ですが、仕方がありません。

int preEval(stack<string> stos){
  string el = "";
  if(stos.empty()){
    return 0;
  }else if(stos.top() IS VALUE){
    string el = stos.top();
    stos.pop();
    return atoi(el.c_str());
  }else if(stos.top() IS OPERATOR){
    int x = preEval(stos);
    int y = preEval(stos);
    return x OPERATOR y;
  }
  return 0;
}

編集

/ 10 5のような式がある場合スタックは要素（上から）/ 10 5、または5 10 /を持っていると想定する必要がありますか？/ 10 5で必要な場合は、文字列を逆方向に読み取る必要があるため、質問するだけです。

4

3 に答える 3

5

より良い解決策は、作業を字句解析と構文解析の2つの段階に分割することだと思います。

字句解析の段階で、各トークンを分類して、それが演算子（、、など）であるか、定数であるか、変数であるかを確認+し-ます。次に、解析されたエンティティを、タイプと追加情報を含む構造にパックします。

コードによって提示される解析段階では、文字列ではなく構造体を操作します。構造を見ると、そのタイプが簡単にわかります。（共通ベースから派生した構造の階層を構築することを選択した場合は、構造内のフィールドまたは構造のタイプのいずれかになります。）

実際、ロジックはJavaとC++の両方で同じである必要があります。

于 2012-08-19T18:41:31.707 に答える
2

次のような機能がある場合：

#include <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <string>

using std::stack;
using std::string;
using std::cerr;

enum Operator {
  operator_none,
  operator_plus,
  operator_minus
};

Operator tokenOperator(const string &token)
{
  if (token=="+") return operator_plus;
  if (token=="-") return operator_minus;
  return operator_none;
}

int applyOperator(Operator op,int x,int y)
{
  switch (op) {
    case operator_plus:  return x+y;
    case operator_minus: return x-y;
    case operator_none:
      break;
  }
  assert(false);
  return 0;
}

bool isValue(const string &token,int &output_value)
{
  char *end = 0;
  errno=0;
  output_value = strtol(token.c_str(),&end,10);
  if (errno!=0) return false;
  return *end=='\0';
}

bool isOperator(const string &token,Operator &output_operator)
{
  output_operator = tokenOperator(token);
  return output_operator!=operator_none;
}

次に、preEvalは次のように実装できます。

int preEval(stack<string> &stos)
{
  if (stos.empty()) return 0;

  string el = stos.top();
  stos.pop();

  int value = 0;
  Operator op = operator_none;

  if (isValue(el,value)) return value;

  if (isOperator(el,op)) {
    int x = preEval(stos);
    int y = preEval(stos);
    return applyOperator(op,x,y);
  }

  return 0;
}
于 2012-08-19T19:44:51.927 に答える
1 
#include <string>
#include <map>

using namespace std;

bool is_value(string s) {
    return s.find_first_not_of("0123456789") == string::npos;
}

int do_add(int x, int y) {
    return x + y;
}

int do_subtract(int x, int y) {
    return x - y;
}

// etc.

typedef int (*binary_op)(int, int);   // Give this function pointer type a nice name
map<string, binary_op> ops;

// Somewhere before the preEval() is ever called
ops["+"] = do_add;
ops["-"] = do_subtract;    // etc.

binary_op lookup_op(string s) {
    map<string, binary_op>::const_iterator it = ops.find(s);
    if (it != ops.end()) {
        return *it;
    } else {
        return NULL;
    }
}

ここで、トークンが演算子であるかどうかを個別にテストし、後でその演算子を実行する代わりに、単一の関数呼び出しを使用して、呼び出す必要のある演算子関数へのポインター（トークンが演算子の場合）またはNULLを取得します。すなわち：

}else if(stos.top() IS OPERATOR){
    int x = preEval(stos);
    int y = preEval(stos);
    return x OPERATOR y;
}

になります

} else {
    binary_op op = lookup_op(stos.top());
    if (binary_op != NULL) {
        stos.pop();   // This fixes the bug I mentioned in my top comment
        int x = preEval(stos);
        int y = preEval(stos);
        return op(x, y);
    } else {
        syntax_error();
    }
}
于 2012-08-19T19:05:00.830 に答える