3

如何解析和评估中缀计算器语法中的表达式?我想到了两种方法。

第一个涉及使用两个堆栈。一个用于数字,另一个用于运算符,我将评估运算符的优先级和关联性,以便弄清楚如何评估表达式。

第二种方法涉及将中缀表达式转换为后缀,我不知道该怎么做。这只是一个想法。目前我设置我的程序的目的是使用第一种方法。

#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

这将是一个漫长的阅读,但无论如何,我将与您分享我用来解析中缀表达式并将其存储为二叉树的算法。不是堆栈,而是二叉树。解析将很容易给出后缀顺序。我并不是说这是最好的算法,但这适用于我的脚本语言。

算法:

我们有一个对二叉树的“当前节点”和“当前表达式”进行操作的方法。这些节点包含一个“数据”字段和一个“类型”字段。

阶段一:简单的东西,比如“4”直接进入节点,我们指定类型为“DATA”,即。按原样使用此信息。

第 2 阶段:现在,让我们考虑以下表达式:

a) 2 + 3

这将转换为以下二叉树:

  +
 / \
2   3

因此,运算符进入节点,操作数进入叶子。将表达式 a) 转换为树很简单:找到运算符,放入树的“当前”节点,指定节点的类型为运算符“PLUS”,剩下的进入树在节点的左边部分,它右边的部分进入右边的树。很好也很简单,使用来自第 1 阶段的信息,两个叶子将是值为 2 和 3 的“DATA”叶子。

第 3 阶段:但是对于更复杂的表达式:

b) 2 * 3 + 4

树将是:

    +
   / \ 4
  *
 / \ 
2   3

所以我们需要将上面的算法修改为:找到具有最高优先级的第一个运算符(考虑 c++ 准则... +(加号)和 -(减号)的优先级为 6,而 *(乘号)的优先级, /(除)和%(取模)为5)在表达式中,将表达式分为两部分(最高优先级的操作数之前和最高优先级的操作数之后)并递归调用这两部分的方法,同时将运算符与当前节点的最高优先级。因此,我们确实创建了一个带有 hdata 的树,例如:

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

在这个阶段,对于调用 ("2*3"),我们会退回到“Stage 2”,对于调用“4”,我们会退回到“Stage 1”。

阶段 4:如果表达式中有括号怎么办?如

c) 2 * (3 + 4)

这将为我们提供树:

      *
     / \
    2   +
       / \
      3   4

我们将算法修改为:

  • 当当前表达式包含在括号中时,从其中删除括号并重新启动算法。当心。(2 + 3 * 4 + 5) 被认为包含在括号中,而 (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

递归下降法是手动实现正确表达式解析器的最简单方法。在这里,编程语言堆栈与您尝试使用的显式堆栈执行相同的操作。用 google 可以找到很多 RD 示例,任何好的编译器书籍都会有一些。

链接的 Wikipedia 页面显示了一个解析器,但没有显示如何添加评估。所以下面是一个完整的 C 语言基本表达式评估器。它可以很容易地包装在 C++ 类中,全局变量成为实例变量。它缺少您在生产系统中需要的功能。例如,当它发现错误时,它就直接退出。C++ 异常将很容易让您展开递归并继续。它还需要防止数字溢出、被零除等,你显然知道如何去做。

递归下降的想法是将所需语言的语法转换为称为 LL(1) 的形式。完成后,就有固定的规则——保证每次都有效——将语法规则转化为程序。我在下面手工完成了这个。有工具可以自动完成。

所以这个评估器很容易扩展。只需添加必要的语法规则,然后对扫描器、解析器和评估代码实施所需的增强。例如,内置函数规则是unsigned_factor -> FUNCTION_NAME ( expr ),其中扫描程序将所有函数名称识别为相同的标记,并且unsigned_factorC 函数被扩充以解析和计算值。

我必须包括一个小型扫描仪才能获得一个工作程序。请注意,一半以上的代码是扫描仪。基本的 RD 解析器很简单。

如果您添加错误恢复,它们会变得更加复杂:跳过错误并继续解析的智能能力,同时仅发出一条准确措辞的错误消息。但是话又说回来,这给任何解析器增加了很多复杂性。

// 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 回答