在编译器内部,计算表达式的值一般是通过表达式树来解决,今天我就给大家介绍一种表达式树的实现。
首先得到一个字符串,里边是一个表达式,算法是:
首先得到表达式的最低优先级的运算符,然后分成左边和右边,然后求值。
#include
#include
#include
#include
#include
#include
using namespace std;
//最大节点数
const int maxn = 1000;
//左右孩子数组,rchild[i]代表i的做孩子的下标
int lchild[maxn],rchild[maxn];
//操作符和操作数
char op[maxn];
//节点数目
int nc = 0;
//表达式
char s[100];
递归算法:
首先寻找字符串表达式里边优先级最低的运算符,然后分为左边和右边继续递归,
当只剩下一个长度的字符串时候结束递归
int build(char *s,int x,int y)
{
int i,c1,c2,p;
//c1指向+-运算符
//c2指向/和*运算符
c1 = c2 = -1;
p = 0;
int u;
if(y-x==1)
{
u = ++nc;
lchild[u] = rchild[u] = 0;
op[u] = s[x];
return u;
}
//如果是括号内部的就忽略
for(i=x;i
{
switch(s[i])
{
case '(':
p++;
break;
case ')':
p--;
break;
case '+':case '-':
if(!p)
c1 = i;
break;
case '*':case '/':
if(!p)
c2 = i;
break;
}
}
//如果最低优先级的不是+-运算符,指向乘除
if(c1<0)
c1 = c2;
//说明整个表达式是在()里边
if(c1<0)
return build(s,x+1,y-1);
u = ++nc;
lchild[u] = build(s,x,c1);
rchild[u] = build(s,c1+1,y);
op[u] = s[c1];
return u;
}
//计算表达式树的值
//后序遍历
int count(int root)
{
int l,r;
if(rchild[root]!=0||lchild[root]!=0)
{
l = count(lchild[root]);
r = count(rchild[root]);
switch(op[root])
{
case '+':
return l+r;
case '-':
return l-r;
case '*':
return l*r;
case '/':
return l/r;
}
}
else
{
return op[root]-'0';
}
}
int main()
{
int x,y;
int len;
strcpy(s,"(2*3+1)");
len = strlen(s);
int root = build(s,0,len);
for(int i=1;i<=5;i++)
{
cout<
}
cout<
return 0;
}
阅读(616) | 评论(0) | 转发(0) |