数据结构之——用C++实现算术表达式求值

基本功能：利用栈实现整数的加减乘除运算。

使用方法：输入表达式之后再输入#表示表达式结束，如下图：

缺点：不能进行小数的运算

代码如下：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define MAXNUM 50
class Stack_for_number
{
private:
float num[MAXNUM];
//运算符栈中元素为float型 考虑除法可能产生的小数
int top;
public:
Stack_for_number(){top=0;}
float push(float);
float pop(void);
float get_top();
};
//运算数栈
class Stack_for_operator
{
private:
char op[MAXNUM];
int top;
public:
Stack_for_operator(){op[0]='#';top=1;}
char push(char);
char pop(void);
char get_top();
};
//运算符栈
float Operate(float a,char b,float c)
{
switch(b)
{
case'+':{return a+c; break;}
case'-':{return a-c; break;}
case'*':{return a*c; break;}
case'/':{return a/c; break;}
default:break;
}
}
//计算当前算式的结果
char Precede(char a,char b)
{
switch(a)
{
case'+':
{
if(b=='+'||b=='-'||b==')'||b=='#')
return '>';
else return '<';
break;
}
case'-':
{
if(b=='+'||b=='-'||b==')'||b=='#')
return '>';
else return '<';
break;
}
case'*':
{
if(b=='(')
return '<';
else return '>';
break;
}
case'/':
{
if(b=='(')
return '<';
else return '>';
break;
}
case'(':
{
if(b==')')
return '=';
else return '<';
break;
}
case')':
{
return '>';
break;
}
case'#':
{
if(b=='#')
return '=';
else return '<';
break;
}
}
}
//运算符优先级比较
float CalculateExpression(Stack_for_number OPND,Stack_for_operator OPTR)
{
char c=getchar();
int n[MAXNUM];
int i=0,j=0,m=0,k=0,tmp=1;
while(c!='#'||OPTR.get_top()!='#')
{	if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='#'&&c!='('&&c!=')')
{
while(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='#'&&c!='('&&c!=')')
{n[i]=int(c)-48;i++;c=getchar();}
// i为当前读入数字位数的计数器
for(j=0;j<i;j++)
{	int ii;
for(ii = 0; ii < i-j-1; ii++)
{tmp *= 10;}
//通过i、j来还原多位数
k=n[j]*tmp;
m=m+k;
tmp=1;
k=0;
//m为还原后的数字（个位数或多位数）
}
OPND.push(m);
m=0;
//m初始化
i=0;
//i初始化
}	//if
else switch(Precede(OPTR.get_top(),c))
{
case'<':
OPTR.push(c);
c=getchar();
break;
case'=':
OPTR.pop();
c=getchar();
break;
case'>':
float x=OPND.pop();float y=OPND.pop();
OPND.push(Operate(y,OPTR.pop(),x));
break;
}
//switch
}
//while
return OPND.get_top();
}
float Stack_for_number::push(float e)
{
if(top==MAXNUM)
{
cout<<"The Stack_for_number is full"<<endl;
return 0;
}
num[top]=e;
top++;
}
float Stack_for_number::pop(void)
{
if(top<0)
{
cout<<"The Stack_for_number is empty"<<endl;
}
top--;
return num[top];
}
char Stack_for_operator::push(char e)
{
if(top==MAXNUM)
{
cout<<"The Stack_for_operator is full"<<endl;
return 0;
}
op[top]=e;
top++;
}
char Stack_for_operator::get_top()
{
if(top<1)
{cout<<"The Stack_for_operator is empty";}
else return op[top-1];
}
float Stack_for_number::get_top()
{
return num[top-1];
}
char Stack_for_operator::pop(void)
{
top--;
if(top<0)
{
cout<<"The Stack_for_operator is empty"<<endl;
}
return op[top];
}
int main()
{
Stack_for_number OPND;
Stack_for_operator OPTR;
cout<<CalculateExpression(OPND,OPTR)<<endl;
}

最后

以上就是昏睡樱桃最近收集整理的关于数据结构之——用C++实现算术表达式求值的全部内容，更多相关数据结构之——用C++实现算术表达式求值内容请搜索靠谱客的其他文章。