也谈表达式分析和计算

Dancefire — Wed, 04 Feb 2009 04:02:00 GMT

昨天看到王博�?/a> Blog中�?a href="http://m.shnenglu.com/d3d/archive/2009/02/03/72851.html">五进制�?/a>�q�篇文章。其中关�?�q�制�?0�q�制的�{换自然没有什么意思，�q�篇文章�l�的代码主要是讨论如何进行表辑ּ�分析和计��的。作者自制了一个Stack�Q��ƈ且用其�Ş成了两个堆栈分别用于存储数值和�q�算�W�。比较典型的表达式处理的�Ҏ��。从实现上看�Q�代码有些臃肿，而且必要的优化很��，另外��是没有充分利用标准提供的便利。比如那个Stack完全没有必要自制�Q�STL提供的std::stack可以很好的完成�Q务�?br>
而今天我要做的是�Q��用boost::spirit来实现同��L��表达式分析和计算。众所周知�Q�boost是C++中质量很高的库，被称为准标准库，因�ؓ其存在的一个很重要的目的就是�ؓ下一代C++库提供预案。目前已�l�有大量的boost库成��Z��C++标准库的一部分。我现在要用的是 Boost的Spirit�?/a>。这个库可以直接在C++代码中撰写EBNF。学�q�编译原理的朋友应该�Ҏ��都很熟悉�Q�这是一�U�比堆栈更灵�zȝ��解析表达式甚至程序的方式�?br>
如果我们要处理四则运��的表达式，那么我们只需要在C++中写入下列EBNF的定义：

    group       = '(' >> expression >> ')';
    factor      = integer | group;
    term        = factor >> *(('*' >> factor) | ('/' >> factor));
    expression  = term >> *(('+' >> term) | ('-' >> term));

我们��构成了�q�个表达式的格式定义�Q�它可以很轻杄��处理下列表达式的�q�算�Q?br>

    12345
    -12345
    +12345
    1 + 2
    1 * 2
    1/2 + 3/4
    1 + 2 + 3 + 4
    1 * 2 * 3 * 4
    (1 + 2) * (3 + 4)
    (-1 + 2) * (3 + -4)
    1 + ((6 * 200) - 20) / 6
    (1 + (2 + (3 + (4 + 5))))

很简单吧�Q?br>
使用�q�yacc或�?lex的朋友对�q�类定义肯定很熟悉。但是所不同的是�Q�他们都是让用户写一个模板，然后用yacc或�?lex处理模板生成相应语言的程序。程序臃肿且很难阅读。而且�׃��不是自己写的�E�序�Q�调整�v来总要�l�过一步手�l�，比较�J�琐�?br>
而��用C++的朋友则不用有这�U�烦��|��Boost的Spirit充分利用了C++强大的语法功能。我们可以直接在�E�序中写入上�q�的表达式定义，然后我们的程序就支持�q�些表达式的处理了。不需要�Q何额外的�E�序处理。所需要的仅仅是include一些头文�g而已。是的，仅仅是include一些头文�g。不要担心需要安装什么额外的东西�Q�或者需要链接什么库�Q�因为Spirit的实现完全是头文件组成的�Q�我们不需要链接�Q何库。把boost的头文�g路径攑ֈ��~�译期中�Q�直接编译就ok了。很��d�y�?br>
下面��是我用Boost Spirit实现的四则运��表辑ּ�的代码，�׃��我的重点是表辑ּ�的解析和计算�Q�因此我没有特别处理五进制到十进制的转换问题。但是添加�v来显然不�ȝ��。我只给��Z��一个五�q�制整数部分的输出。如果表辑ּ�出错�Q�可以直接用��头指出哪里有错。很方便调试�Q�）而且代码量是原文章的五分之一。编译后也仅仅是35KB�Q�也不是很臃肿的�?br>
大家多了解标准库�Q�多了解Boost�Q�C++的编码也是很有趣味的�?br>

#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>

#include <iostream>
#include <string>
#include <cmath>
#include <limits>

using namespace boost::spirit;
using namespace boost::spirit::qi;
using namespace boost::spirit::ascii;
using namespace boost::spirit::arg_names;

template <typename Iterator>
struct calculator : grammar<Iterator, double(), space_type>
{
    calculator() : calculator::base_type(expression)
    {
        expression = term[_val = _1]
        >> *( ('+' >> term[_val += _1]) | ('-' >> term[_val -= _1]) );

        term = factor[_val = _1]
        >> *( ('*' >> factor[_val *= _1]) | ('/' >> factor[_val /= _1]) );

        factor = double_[_val = _1]    | '(' >> expression[_val = _1] >> ')'
            |   ('-' >> factor[_val = -_1]) | ('+' >> factor[_val = _1]);
    }

    rule<Iterator, double(), space_type> expression, term, factor, number;
};

//    http://www.jb.man.ac.uk/~slowe/cpp/itoa.html
std::string itoa(int value, int base) {
    const int MAX_DIGITS = 35;
    const char* DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz";
    std::string buf;
    buf.reserve( MAX_DIGITS ); // Pre-allocate enough space.
    if (base < 2 || base > 36) return buf;
    int quotient = value;
    do {
        buf.push_back(DIGITS[ std::abs(quotient % base) ]);
        quotient /= base;
    } while ( quotient );
    if ( value < 0) buf.push_back('-');
    std::reverse( buf.begin(), buf.end() );
    return buf;
}

int main(int argc, char* argv[])
{
    std::cout << "误��入一个表辑ּ��Q�如�Q?+2.5*(6-25/4)-8.32" << std::endl << std::endl;
    std::cout << "或输入q退出�?/span>" << std::endl << std::endl;
    std::cout << "> ";
    calculator<std::string::const_iterator> calc;

    std::string str;
    double result;
    while (std::getline(std::cin, str))
    {
        if (str.empty() || str[0] == 'q' || str[0] == 'Q')
            break;

        std::string::const_iterator iter = str.begin();
        std::string::const_iterator end = str.end();
        bool r = phrase_parse(iter, end, calc, result, space);

        if (r && iter == end)
        {
            std::cout << "输入语法正确�Q�表辑ּ�的��gؓ�Q?/span>";

            if (result == std::numeric_limits<double>::infinity())
                std::cout << "∞";
            else if (result == std::numeric_limits<double>::quiet_NaN())
                std::cout << "�l�果非数�?/span>";
            else
            {
                std::cout << result << std::endl;
                std::cout << "整数部分转换�?�q�制为：" << itoa(static_cast<int>(result), 5);
            }
            std::cout << std::endl;

        }
        else
        {
            std::cout << "[输入的表辑ּ�错误]" << std::endl;
            std::cout << str << std::endl;
            std::cout << std::string(iter - str.begin(), '-') << "^" << std::endl;
        }
        std::cout << std::endl << "> ";
    }
    return 0;
}

�q�行�l�果如下�Q?br>

误��入一个表辑ּ��Q�如�Q?/span>3+2.5*(6-25/4)-8.32

或输入q退出�?br>
> 3+2.5*(6-25/4)-8.32
输入语法正确�Q�表辑ּ�的��gؓ�Q?/span>-5.945
整数部分转换�?�q�制为：-10

> -6
输入语法正确�Q�表辑ּ�的��gؓ�Q?/span>-6
整数部分转换�?�q�制为：-11

> 6
输入语法正确�Q�表辑ּ�的��gؓ�Q?/span>6
整数部分转换�?�q�制为：11

> 1/0
输入语法正确�Q�表辑ּ�的��gؓ�Q?#8734;

> 23 + 4 ((5)-3* 6) + (-1)
[输入的表辑ּ�错误]
23 + 4 ((5)-3* 6) + (-1)
-------^

> 23 + 4 ( ( 5-3*6) +1)
[输入的表辑ּ�错误]
23 + 4 ( ( 5-3*6) +1)
-------^

> 23 + 4 + ( -5 *3)
输入语法正确�Q�表辑ּ�的��gؓ�Q?/span>12
整数部分转换�?�q�制为：22

>

Dancefire 2009-02-04 12:02 发表评论

国产精品国产三级国产aⅴ9色,亚洲视频网在线直播,亚洲日本一区二区三区

也谈表达式分析和计算