表达式求值的关键点在于中缀表达式转后缀表达式，算法书上都有明确介绍就不多说了。动手实现了一个表达式解析器，支持括号、多位整数以及表达式合法性判断。今天的状态实在很差，本想对表达式进行合法性判断的时候使用一些类似哈希表的技巧，比如使用一个大的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
小四 阅读(688)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构