表达式求值的关键点在于中缀表达式转后缀表达式,算法书上都有明确介绍就不多说了。动手实现了一个表达式解析器,支持括号、多位整数以及表达式合法性判断。今天的状态实在很差,本想对表达式进行合法性判断的时候使用一些类似哈希表的技巧,比如使用一个大的bool数组,合法字符ASC码对应的项设置为1,比如可以直接判断CHARS['+']是否为true,省去查找的时间。后来发现一共就支持那几个字符,这样做未免有点太矫情了。头脑乱乱的,为了支持多位整数,用了string,感觉怪怪的。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//* -------------------------------------------------------------------------
// 文件名 : ExpParser.h
// 创建者 : dj
// 创建时间 : 2008-1-4 18:35
// 功能描述 : 表达式求值
// -----------------------------------------------------------------------*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#ifndef __EXPPARSER_H__
#define __EXPPARSER_H__
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <vector>
#include <string>
using namespace std;
typedef vector<string> strings;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class ExpParser
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
int CalcExp(const char* sExp) //解析表达式并计算
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (!CheckExp(sExp))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 0;
}
strings inExp;
strings postExp;
GetInExp(inExp, sExp);
GetPostExp(postExp, inExp);
return CalcPostExp(postExp);
}
private:
inline int OptrPRI(const string& s) //得到运算符优先级
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
switch(s[0])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
case '#':
return 0;
default:
return -1;
}
}
inline bool IsNum(const char* s) //判断是否数字
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return (*s<='9'&&*s>='0');
}
inline bool IsNum(const string& s)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return (IsNum(&s[0]));
}
inline bool IsOptr(const char* s)//判断是否运算符
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
switch(*s)
{
case '+':
case '-':
case '*':
case '/':
return true;
default:
return false;
}
}
int Calc(const string& s1, const string& s2, const string& optr)//根据运算符计算结果
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int n1 = atoi(s1.c_str());
int n2 = atoi(s2.c_str());
if (optr == "+")
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return n1+n2;
}
else if (optr == "-")
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return n1-n2;
}
else if (optr == "*")
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return n1*n2;
}
else if (optr == "/")
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return n1/n2;
}
assert(false);
return 0;
}
int CalcPostExp(const strings& postExp) //计算后缀表达式的结果
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int n = 0;
strings::const_iterator it = postExp.begin();
stack<string> st; //运算数临时栈
for(; it != postExp.end(); it++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(IsNum(*it)) //数字,直接入栈
st.push(*it);
else //运算符,取栈顶两元素运算,结果进栈
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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) //检查表达式合法性
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
stack<char> st;
const char* p = sExp;
bool bPrevOptr = true;
while(*p!=NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (IsOptr(p))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (bPrevOptr)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<"illegal expression"<<endl;
return false;
}
bPrevOptr = true;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
bPrevOptr = false;
if (*p=='(')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
st.push(*p);
}
else if (*p==')')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(st.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<"a '(' is expected"<<endl;
return false;
}
st.pop();
}
else if (!IsNum(p))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<"unexpected symbol"<<endl;
return false;
}
}
p++;
}
if (!st.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<"a ')' is expected"<<endl;
return false;
}
return true;
}
void GetInExp(strings& inExp, const char* sExp)//根据原始字符串得到中缀表达式
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
string s;
int nLen = strlen(sExp);
for (int i = 0; i < nLen; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (IsNum(&sExp[i]))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s += sExp[i];
if (!IsNum(&sExp[i+1]))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
inExp.push_back(s);
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s = sExp[i];
inExp.push_back(s);
s.erase();
}
}
}
void GetPostExp(strings& postExp, const strings& inExp)//根据中缀表达式得到后缀表达式
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
stack<string> st; //临时运算符栈
st.push("#");
strings::const_iterator it = inExp.begin();
for(; it != inExp.end(); it++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (IsNum(*it)) //数字直接加入后缀表达式
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
postExp.push_back(*it);
}
else if (*it == "(") //左括号,入运算符栈
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
st.push(*it);
}
else if (*it == ")") //右括号,到左括号之间的运算符出栈加入后缀表达式
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
while(st.top()!="(")
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
postExp.push_back(st.top());
st.pop();
}
st.pop();
}
else //其它运算符,出栈直到大于栈顶元素优先级
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int nPRI = OptrPRI(*it);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while (nPRI<=OptrPRI(st.top()))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
postExp.push_back(st.top());
st.pop();
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
st.push(*it);
}
}
while (!st.empty()) //栈内剩余运算符出栈加入后缀表达式
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (st.top()!="#")
postExp.push_back(st.top());
st.pop();
}
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#endif
int main(int argc, char* argv[])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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
小四 阅读(682)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构