验证中...
私信发送成功
语言: C/C++
分类: 编程语言基础
最后更新于 2018-01-14 12:41
算术表达式求值.cpp
原始数据 复制代码
/***链栈实现表达式求值***/
#include<iostream>
#include <cstring>
using namespace std;
const char oper[7] = {'+','-','*','/','(',')','#'};
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int SElemType;
typedef int Status;
typedef struct SNode{
int data;
struct SNode *next;
}SNode,*LinkStack;
Status InitStack(LinkStack &S)
{
S = NULL;
return OK;
}
bool StackEmpty(LinkStack S)
{
if(!S)
return true;
return false;
}
Status Push(LinkStack &S,SElemType e)
{
SNode *p = new SNode;
if(!p)
{
return OVERFLOW;
}
p->data = e;
p->next = S;
S = p;
return OK;
}
Status Pop(LinkStack &S,SElemType &e)
{
SNode *p;
if(!S)
return ERROR;
e = S->data;
p = S;
S = S->next;
delete p;
return OK;
}
Status GetTop(LinkStack &S,SElemType &e)
{
if(!S)
return ERROR;
e = S->data;
return OK;
}
bool In(char ch)
{//判断ch是否为运算符
for(int i = 0;i < 7; i++)
{
if(ch == oper[i])
{
return true;
}
}
return false;
}
char Precede(char theta1,char theta2)
{//判断运算符优先级
if((theta1 == '('&&theta2 == ')')||(theta1 == '#'&&theta2 == '#'))
{
return '=';
}
else if(theta1 == '('||theta1 == '#'||theta2 == '('
||(theta1 == '+'||theta1 == '-')&&(theta2 == '*'||theta2 == '/'))
{
return '<';
}
else
return '>';
}
int Operate(int first,char theta,int second)
{//计算两数运算结果
switch(theta)
{
case '+':
return first + second ;
case '-':
return first - second ;
case '*':
return first * second;
case '/':
return first / second;
}
return 0;
}
int EvaluateExpression()
{
// 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈,
// OP 为运算符集合
LinkStack OPTR,OPND;
char ch[30];
int a,b,res = 0,x,top=0,thera;
InitStack (OPTR);
Push (OPTR,int('#'));
InitStack (OPND);
cin>>ch;
int i = 0,tmp;
while (ch[i] != '#' || (GetTop(OPTR,top) ,char(top)!= '#') )
{
//cout<<ch[2]<<endl;
if(!In(ch[i]))
{
//cout<<ch[i]<<endl;
tmp = ch[i]-'0';
// cout<<tmp<<endl;
while(!In(ch[++i])){
tmp *= 10;
tmp += ch[i]-'0';
}
Push(OPND, tmp);
//cout<<tmp<<endl;
} // ch不是运算符则进栈
else
{
GetTop(OPTR, top);
// cout<<char(top)<<ch[i]<<endl;
switch (Precede(char(top),ch[i]))
{ //比较OPTR的栈顶元素和ch的优先权
case '<': //当前字符ch压入OPTR栈,读入下一字符ch
Push(OPTR, ch[i]);
//cout<<ch[i]<<endl;
i++;
break;
case '>': //弹出OPTR栈顶的运算符进行相应运算,并将运算结果入栈
Pop(OPTR, thera);
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, Operate(a, char(thera), b));
//cout<<Operate(a, char(thera), b)<<endl;
break;
case '=': //脱括号并接收下一字符
Pop(OPTR, x);
i++;
break;
} // switch
}
} // while
if(GetTop(OPND,res))
return res;
return 0;
} // EvaluateExpression
int main()
{
cout<<"请输入要计算的表达式,以#结束):"<<endl;
int result = EvaluateExpression();
cout<<"计算结果为"<<result<<endl;
return 0;
}

评论列表( 0 )

你可以在登录后,对此项目发表评论

6_float_left_people 6_float_left_close