C++计算四则运算表达式程序

汤忤柳 · 发表于 2018-12-6 17:31:39

欢迎访问技术宅的结界，请注册或者登录吧。

您需要登录才可以下载或查看，没有账号？立即注册→加入我们

×

注1：这是本人2016年的旧文，特发至宝地，望抛砖引玉。

注2：源码：https://github.com/tomwillow/ExpressionCalc

注3：表达式树计算我是学习自中国大学MOOC 台湾清华韩永楷老师的《数据结构》课程。有兴趣的同学可以看视频进行学习。

注4：这个表达式树的原理我后来用在了编写连杆机构仿真中的方程计算类里面，能以字符串输入求解线性/非线性方程，并且我定义了几个类似于MATLAB的接口，可以单独把计算类抽出来用。详情见Github：
https://github.com/tomwillow/Linkage-Mechanism-Laboratory
————

最近在学数据结构，刚学完Expression Tree，解答了我多年的疑惑。以前就想写一个二十四点的小游戏，计算机发4张牌，玩家在规定时间内想出4张牌任意四则运算后得到24的表达式。框架搭好，也可以发牌了，电脑怎么答题可以遍历所有可能性，得到24就中止。但玩家输入表达式，怎么计算出值是关键问题。现在终于知道解法了。

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int isNumber(char c);
/* 单个元素 */
struct Element
{
int type;//0:数字 1:运算符
int value;//数字的值
char operate[5];//运算符
int op_num;//操作数个数
bool left2right;//运算顺序左结合
};
/* 返回运算符结合性 */
bool isLeft2Right(char c)
{
switch (c)
{
case '+':
case '-':
case '*':
case '/':
case '&':
case '|':
case '%':return true;
case '^':return false;
}
}
/* 返回运算符的优先级 */
int Rank(char s[])
{
switch (s[0])
{
case '(':return 0;
case ')':return 0;//左右括号优先级小是为了不被其余任何运算符挤出
case '+':
case '-':return 5;//低优先级将挤出高优先级
case '*':
case '/':return 10;
case '^':return 11;
case '&':
case '|':return 12;
case '%':return 15;//取余运算
}
int err=-1;
if (isNumber(s[0])) err=0;
return err;
}
/* 是运算符 */
int isOperator(char c)
{
switch (c)
{
case '(':
case ')':return 10;
case '+':
case '-':
case '*':
case '/':
case '^':
case '&':
case '|':
case '%':return 1;
}
return 0;
}
/* 有效性检查（返回0则出现异常字符） */
int isLegal(char c)
{
if (isNumber(c)) return 1;
if (isOperator(c)) return 1;
return 0;
}
int isNumber(char c)
{
if (c>='0' && c<='9')
return 1;
else
return 0;
}
/* 由位数得到应该相乘的倍数如digit=2返回100 */
int digit2num(int digit)
{
int temp=1;
digit--;
while (digit)
{
temp*=10;
digit--;
}
return temp;
}
/*由in order队列得到post order队列*/
int InQueue2PostQueue(queue<Element> *post,queue<Element> *in)//返回0:正常 1:括号不配对
{
int sq_err=0;
stack<Element> temp;
while (in->size()>0)
{
if (in->front().type==0)
{
post->push(in->front());
in->pop();
}
else
{
if (in->front().operate[0]=='(') //左括号直接入栈
{
temp.push(in->front());
in->pop();
sq_err++;
}
else
{
if (in->front().operate[0]==')')//出现右括号
{
while (temp.size()>0)
{
if (temp.top().operate[0]=='(')
{
temp.pop();
sq_err--;
break;
}
else
{
post->push(temp.top());
temp.pop();
}
}
in->pop();
}
else//不是括号
{
if (temp.size()>0 && temp.top().left2right==true)//左结合
while (temp.size()>0 && Rank(in->front().operate)<=Rank(temp.top().operate))//临时栈有内容，且新进符号优先级低，则挤出高优先级及同优先级符号
{
post->push(temp.top());//符号进入post队列
temp.pop();
}
else//右结合
while (temp.size()>0 && Rank(in->front().operate)<Rank(temp.top().operate))//临时栈有内容，且新进符号优先级低，则挤出高优先级，但不挤出同优先级符号（因为右结合）
{
post->push(temp.top());//符号进入post队列
temp.pop();
};
temp.push(in->front());//高优先级已全部挤出，当前符号入栈
in->pop();
}
}
}
}
while (temp.size()>0)
{
post->push(temp.top());
temp.pop();
}
return sq_err;
}
/*由字符串表达式得到in order队列*/
int Str2Queue(queue<Element> *inorder,char expression[])
{
int err=0;
Element tempe;
int a,b;
int type,num,sign=1;
for (int i=0;i<(int)strlen(expression);)
{
num=0;
type=isNumber(expression[i]);
if (type) a=i;
while (isNumber(expression[i])&&i<(int)strlen(expression))
{
i++;
}
if (type)//数字
{
b=i-a;//位数
while (b)
{
num+=(expression[a]-'0')*digit2num(b);
a++;
b--;
}
tempe.type=0;
tempe.value=num*sign;
sign=1;//sign符号正常化
tempe.operate[0]='\0';
(*inorder).push(tempe);
}
else//不是数字
{
if ( (expression[i]=='-' && i==0)||(expression[i]=='-' && isOperator(expression[i-1])) )//
{
sign*=-1;
}
else
{
/* 非法性判定 */
if (isLegal(expression[i])!=1) {err=-1;break;}//出现非法字符
if (i==0 && isOperator(expression[i])) {err=-1;break;}//首字符出现非-的符号
if (i+1<(int)strlen(expression) && isOperator(expression[i])==1 && expression[i+1]==')') {err=-1;break;}//出现*)形式
if (i-1>=0 && isOperator(expression[i])==1 && (expression[i-1]=='(' || isOperator(expression[i-1])==1)) {err=-1;break;}//出现(*形式或**形式
tempe.type=1;
tempe.value=0;
tempe.operate[0]=expression[i];
tempe.operate[1]='\0';
tempe.left2right=isLeft2Right(expression[i]);
tempe.op_num=2;
(*inorder).push(tempe);
}
i++;
}
}
return err;
}
/*由运算符c及a,b计算出值*/
int CalcNum(int a,int b,char c)
{
switch (c)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
case '%':return a%b;
case '&':return a&b;
case '|':return a|b;
case '^':return (int)pow((double)a,(double)b);
}
}
/*由post order序列计算出值*/
int Calc(queue<Element> *post)
{
Element tempe;
stack<Element> temp;
int a,b;
while (post->size()>0)
{
if (post->front().type==1)//运算符
{
b=temp.top().value;temp.pop();
a=temp.top().value;temp.pop();
tempe.type=0;tempe.operate[0]='\0';tempe.value=CalcNum(a,b,post->front().operate[0]);
temp.push(tempe);
post->pop();
}
else
{
temp.push(post->front());
post->pop();
}
}
return temp.top().value;
}
int main()
{
cout<<"----- 表达式运算Demo -----"<<endl;
cout<<"作者：Tom Willow 2016.03.17"<<endl;
cout<<"功能：输入整数表达式计算出值。"<<endl;
cout<<"支持：加+ 减- 乘* 除/ 幂运算^ 求余% 按位与& 按位或|"<<endl;
cout<<"举例：输入6-5*(4-3+(2+1)) 返回-14"<<endl;
char expression[100];
while (1)
{
cout<<">>";
cin>>expression;
/* 1.字符串转换为in order队列 */
queue<Element> inorder,postorder;
if (Str2Queue(&inorder,expression)!=0)
{
cout<<"表达式非法。"<<endl;
}
else
/* 2.in order队列转换为post order队列 */
if (InQueue2PostQueue(&postorder,&inorder))
{
cout<<"括号不匹配。"<<endl;
}
else
/* 3.由post order队列计算出值 */
cout<<Calc(&postorder)<<endl;
}
}

复制代码

Golden Blonde · 发表于 2018-12-12 00:58:42

代码不错，通过学习你的代码让我又解锁了一个技能。

账号		自动登录	找回密码
密码			立即注册→加入我们