缀计算器表达式解析器(Infix Calculator Expression Parser)

2019-07-05 03:46发布

站内文章 / 后端开发

43 0

贼婆χ

女 | 书童

私信

如何分析和评估在缀计算器的语法表达？我认为有两种方式。

首届涉及使用两个栈。一个是数字，另一个是运营商，我会评估，以找出如何计算表达式运算符优先级和关联。

第二种方法是中缀表达式转换为后缀，我不知道如何我会去这样做。这只是一个想法。目前，我建立了我的计划与打算用第一方法。

#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;
}

Answer 1:

这将是一个漫长的读取，但无论如何，我将与大家分享我用它来解析缀表达式并将其存储为一个二叉树的算法。不能叠加，但二叉树。解析会轻易放弃后缀顺序。我不说这是最好的算法存在，但是这个工作对我的脚本语言。

该算法：

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

第1阶段：简单的东西，如“4”直接进入的节点，我们指定类型为“数据”，即。利用这些信息，因为它是。

第2阶段：现在，让我们考虑下面的表达式：

a) 2 + 3

这将被改造成以下二叉树：

  +
 / \
2   3

因此，运营商进入节点和操作数进入叶子。 Transofrming表达）移动到树很简单：找到经营者，就把树的“当前”节点，指定节点是运营商“PLUS”，什么类型是左它进入树到节点的左侧部分，什么是正确的它进入右树。尼斯和简单，使用来自阶段1中的两个叶子的信息将是“DATA”叶子具有值2和3。

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

b) 2 * 3 + 4

树将是：

因此，我们需要修改上面下面的算法：查找具有最高优先级的第一家运营商（考虑到c ++指南... +（加）和优先级 - （减号）是6，而*的优先级（乘） /（除）和％（模）为5）中的表达，划分表达成两个部分（具有最高的优先级和与最高优先级的操作数后的操作数之前），并调用递归方法为两个部分，而将所述操作者最高优先级到当前节点。所以，我们确实创造了一个树机智HDATA喜欢：

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

并且在这个阶段，我们回落到“第2阶段”，为通话（“2 * 3”）和“第1阶段”为呼叫“4”。

第四阶段：如果有在表达paranthesis？如

c) 2 * (3 + 4)

这将使我们的树：

我们修改了算法是这样的：

而目前的表达被封闭在paranthesis从中取出paranthesis并重新启动算法。小心。（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行。

Answer 2:

的方法递归下降是实施用手正确的表达式分析器的简单的方法。这里的编程语言栈做同样的事情，你想使用显式堆栈。有与谷歌找到许多例子RD，任何好的编译器的书都会有一些。

链接的维基百科页面显示了一个分析器，但不知道如何添加评价。所以下面是C中的完整的基本的表达式求值器它可以被容易地包裹在与全局成为实例变量C ++类。它缺少你需要在生产系统中的功能。例如，当它发现一个错误，它只是退出。 C ++异常将很容易让你放松身心的递归和继续。还需要对数值溢出保护，除以零等，这显然你知道该怎么做。

的递归下降的想法是所希望的语言的语法变换为称为LL（1）的形式。如果这样做了，有固定的规则 - 保证的广告工作的每一次 - 用于将语法规则进入程序。我一直用手工完成这下面。有工具来自动执行。

所以这个评估是非常容易扩展。只需添加必要的语法规则，然后实现需要改进的扫描仪，解析器和评估代码。例如，内置函数规则是unsigned_factor -> FUNCTION_NAME ( expr ) ，其中扫描仪识别所有的功能名称作为同样与unsigned_factor C函数被扩充来分析和计算值。

我必须包括一个小型扫描仪获得的工作计划。注意：超过一半的代码是扫描仪。基本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

文章来源: Infix Calculator Expression Parser

标签： c++ parsing stack expression calculator

贼婆χ

女 | 书童

私信

收藏的人(0)

Ta的文章更多文章

0条评论

还没有人评论过~