昨天看到
王博煒 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))))
很簡(jiǎn)單吧？
使用過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
>