昨天看到 王博煒 Blog中《五進(jìn)制》這篇文章。其中關(guān)于5進(jìn)制到10進(jìn)制的轉(zhuǎn)換自然沒有什么意思，這篇文章給的代碼主要是討論如何進(jìn)行表達(dá)式分析和計(jì)算的。作者自制了一個(gè)Stack，并且用其形成了兩個(gè)堆棧分別用于存儲(chǔ)數(shù)值和運(yùn)算符。比較典型的表達(dá)式處理的方法。從實(shí)現(xiàn)上看，代碼有些臃腫，而且必要的優(yōu)化很少，另外就是沒有充分利用標(biāo)準(zhǔn)提供的便利。比如那個(gè)Stack完全沒有必要自制，STL提供的std::stack<T>可以很好的完成任務(wù)。

而今天我要做的是，使用boost::spirit來實(shí)現(xiàn)同樣的表達(dá)式分析和計(jì)算。眾所周知，boost是C++中質(zhì)量很高的庫，被稱為準(zhǔn)標(biāo)準(zhǔn)庫，因?yàn)槠浯嬖诘囊粋€(gè)很重要的目的就是為下一代C++庫提供預(yù)案。目前已經(jīng)有大量的boost庫成為了C++標(biāo)準(zhǔn)庫的一部分。我現(xiàn)在要用的是Boost的Spirit庫。這個(gè)庫可以直接在C++代碼中撰寫EBNF。學(xué)過編譯原理的朋友應(yīng)該對(duì)此都很熟悉，這是一種比堆棧更靈活的解析表達(dá)式甚至程序的方式。

如果我們要處理四則運(yùn)算的表達(dá)式，那么我們只需要在C++中寫入下列EBNF的定義：

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

我們就構(gòu)成了這個(gè)表達(dá)式的格式定義，它可以很輕松的處理下列表達(dá)式的運(yùn)算：

    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))))

很簡單吧？

使用過yacc或者*lex的朋友對(duì)這類定義肯定很熟悉。但是所不同的是，他們都是讓用戶寫一個(gè)模板，然后用yacc或者*lex處理模板生成相應(yīng)語言的程序。程序臃腫且很難閱讀。而且由于不是自己寫的程序，調(diào)整起來總要經(jīng)過一步手續(xù)，比較繁瑣。

而使用C++的朋友則不用有這種煩惱，Boost的Spirit充分利用了C++強(qiáng)大的語法功能。我們可以直接在程序中寫入上述的表達(dá)式定義，然后我們的程序就支持這些表達(dá)式的處理了。不需要任何額外的程序處理。所需要的僅僅是include一些頭文件而已。是的，僅僅是include一些頭文件。不要擔(dān)心需要安裝什么額外的東西，或者需要鏈接什么庫，因?yàn)镾pirit的實(shí)現(xiàn)完全是頭文件組成的，我們不需要鏈接任何庫。把boost的頭文件路徑放到編譯期中，直接編譯就ok了。很輕巧。

下面就是我用Boost Spirit實(shí)現(xiàn)的四則運(yùn)算表達(dá)式的代碼，由于我的重點(diǎn)是表達(dá)式的解析和計(jì)算，因此我沒有特別處理五進(jìn)制到十進(jìn)制的轉(zhuǎn)換問題。但是添加起來顯然不麻煩。我只給出了一個(gè)五進(jìn)制整數(shù)部分的輸出。如果表達(dá)式出錯(cuò)，可以直接用箭頭指出哪里有錯(cuò)。很方便調(diào)試：） 而且代碼量是原文章的五分之一。編譯后也僅僅是35KB，也不是很臃腫的。

大家多了解標(biāo)準(zhǔn)庫，多了解Boost，C++的編碼也是很有趣味的。

#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ǐng)輸入一個(gè)表達(dá)式，如：3+2.5*(6-25/4)-8.32" << std::endl << std::endl;
    std::cout << "或輸入q退出。" << 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 << "輸入語法正確，表達(dá)式的值為：";

            if (result == std::numeric_limits<double>::infinity())
                std::cout << "∞";
            else if (result == std::numeric_limits<double>::quiet_NaN())
                std::cout << "結(jié)果非數(shù)值";
            else
            {
                std::cout << result << std::endl;
                std::cout << "整數(shù)部分轉(zhuǎn)換為5進(jìn)制為：" << itoa(static_cast<int>(result), 5);
            }
            std::cout << std::endl;

        }
        else
        {
            std::cout << "[輸入的表達(dá)式錯(cuò)誤]" << std::endl;
            std::cout << str << std::endl;
            std::cout << std::string(iter - str.begin(), '-') << "^" << std::endl;
        }
        std::cout << std::endl << "> ";
    }
    return 0;
}




運(yùn)行結(jié)果如下：

請(qǐng)輸入一個(gè)表達(dá)式，如：3+2.5*(6-25/4)-8.32

或輸入q退出。

> 3+2.5*(6-25/4)-8.32
輸入語法正確，表達(dá)式的值為：-5.945
整數(shù)部分轉(zhuǎn)換為5進(jìn)制為：-10

> -6
輸入語法正確，表達(dá)式的值為：-6
整數(shù)部分轉(zhuǎn)換為5進(jìn)制為：-11

> 6
輸入語法正確，表達(dá)式的值為：6
整數(shù)部分轉(zhuǎn)換為5進(jìn)制為：11

> 1/0
輸入語法正確，表達(dá)式的值為：∞

> 23 + 4 ((5)-3* 6) + (-1)
[輸入的表達(dá)式錯(cuò)誤]
23 + 4 ((5)-3* 6) + (-1)
-------^

> 23 + 4 ( ( 5-3*6) +1)
[輸入的表達(dá)式錯(cuò)誤]
23 + 4 ( ( 5-3*6) +1)
-------^

> 23 + 4 + ( -5 *3)
輸入語法正確，表達(dá)式的值為：12
整數(shù)部分轉(zhuǎn)換為5進(jìn)制為：22

>