表達式求值的關鍵點在于中綴表達式轉后綴表達式，算法書上都有明確介紹就不多說了。動手實現了一個表達式解析器，支持括號、多位整數以及表達式合法性判斷。今天的狀態實在很差，本想對表達式進行合法性判斷的時候使用一些類似哈希表的技巧，比如使用一個大的bool數組，合法字符ASC碼對應的項設置為1，比如可以直接判斷CHARS['+']是否為true,省去查找的時間。后來發現一共就支持那幾個字符，這樣做未免有點太矯情了。頭腦亂亂的，為了支持多位整數，用了string，感覺怪怪的。
/**//* -------------------------------------------------------------------------
// 文件名 ： ExpParser.h
// 創建者 ： dj
// 創建時間 ： 2008-1-4 18:35
// 功能描述 ： 表達式求值
// -----------------------------------------------------------------------*/
#ifndef __EXPPARSER_H__
#define __EXPPARSER_H__
#include <vector>
#include <string>
using namespace std;
typedef vector<string> strings;
class ExpParser
{
public:
int CalcExp(const char* sExp) //解析表達式并計算
{
if (!CheckExp(sExp))
{
return 0;
}
strings inExp;
strings postExp;
GetInExp(inExp, sExp);
GetPostExp(postExp, inExp);
return CalcPostExp(postExp);
}
private:
inline int OptrPRI(const string& s) //得到運算符優先級
{
switch(s[0])
{
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
case '#':
return 0;
default:
return -1;
}
}
inline bool IsNum(const char* s) //判斷是否數字
{
return (*s<='9'&&*s>='0');
}
inline bool IsNum(const string& s)
{
return (IsNum(&s[0]));
}
inline bool IsOptr(const char* s)//判斷是否運算符
{
switch(*s) {
case '+':
case '-':
case '*':
case '/':
return true;
default:
return false;
}
}
int Calc(const string& s1, const string& s2, const string& optr)//根據運算符計算結果
{
int n1 = atoi(s1.c_str());
int n2 = atoi(s2.c_str());
if (optr == "+")
{
return n1+n2;
}
else if (optr == "-")
{
return n1-n2;
}
else if (optr == "*")
{
return n1*n2;
}
else if (optr == "/")
{
return n1/n2;
}
assert(false);
return 0;
}
int CalcPostExp(const strings& postExp) //計算后綴表達式的結果
{
int n = 0;
strings::const_iterator it = postExp.begin();
stack<string> st; //運算數臨時棧
for(; it != postExp.end(); it++)
{
if(IsNum(*it)) //數字，直接入棧
st.push(*it);
else //運算符，取棧頂兩元素運算，結果進棧
{
string s1 = st.top(); st.pop();
string s2 = st.top(); st.pop();
n = Calc(s2, s1, *it);
char a[255];
itoa(n, a, 10);
st.push(a);
}
}
return n;
}
bool CheckExp(const char* sExp) //檢查表達式合法性
{
stack<char> st;
const char* p = sExp;
bool bPrevOptr = true;
while(*p!=NULL)
{
if (IsOptr(p))
{
if (bPrevOptr)
{
cout<<"illegal expression"<<endl;
return false;
}
bPrevOptr = true;
}
else
{
bPrevOptr = false;
if (*p=='(')
{
st.push(*p);
}
else if (*p==')')
{
if(st.empty())
{
cout<<"a '(' is expected"<<endl;
return false;
}
st.pop();
}
else if (!IsNum(p))
{
cout<<"unexpected symbol"<<endl;
return false;
}
}
p++;
}
if (!st.empty())
{
cout<<"a ')' is expected"<<endl;
return false;
}
return true;
}
void GetInExp(strings& inExp, const char* sExp)//根據原始字符串得到中綴表達式
{
string s;
int nLen = strlen(sExp);
for (int i = 0; i < nLen; i++)
{
if (IsNum(&sExp[i]))
{
s += sExp[i];
if (!IsNum(&sExp[i+1]))
{
inExp.push_back(s);
}
}
else
{
s = sExp[i];
inExp.push_back(s);
s.erase();
}
}
}
void GetPostExp(strings& postExp, const strings& inExp)//根據中綴表達式得到后綴表達式
{
stack<string> st; //臨時運算符棧
st.push("#");
strings::const_iterator it = inExp.begin();
for(; it != inExp.end(); it++)
{
if (IsNum(*it)) //數字直接加入后綴表達式
{
postExp.push_back(*it);
}
else if (*it == "(") //左括號，入運算符棧
{
st.push(*it);
}
else if (*it == ")") //右括號，到左括號之間的運算符出棧加入后綴表達式
{
while(st.top()!="(")
{
postExp.push_back(st.top());
st.pop();
}
st.pop();
}
else //其它運算符，出棧直到大于棧頂元素優先級
{
int nPRI = OptrPRI(*it);
while (nPRI<=OptrPRI(st.top()))
{
postExp.push_back(st.top());
st.pop();
}
st.push(*it);
}
}
while (!st.empty()) //棧內剩余運算符出棧加入后綴表達式
{
if (st.top()!="#")
postExp.push_back(st.top());
st.pop();
}
}
};
#endif
int main(int argc, char* argv[])
{
ExpParser ep;
int n = ep.CalcExp("7*(857+142*1000)");
cout<<n<<endl;
return 0;
}
神奇地數,142857,
142857*1=142857
142857*2=285714
142857*3=428571
142857*4=571428
142857*5=714285
142857*6=857142
142857*7=999999
它發現于埃及金字塔內，
它證明一星期有7天，
它自我累加一次，
就由它的6個數字，
依順序輪值一次，
到了第7天，
它們就放假，
由999999去代班。
新年第一個周末快樂。
posted on 2008-01-04 19:59
小四 閱讀(716)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構