当前位置：首页 > news >正文

11.9 表达式求值

news 来源：原创 2024/5/19 6:14:00

11.9 表达式求值

【问题描述】给出一个合法的表达式，请输出它的计算结果。表达式满足以下条件：
① 只有+、-、*、/、^（乘方）运算和括号。
② 所有操作数都是非负数。计算过程中（包括最后结果）可能会出现负数，但不会超过 int 的表示范围。
③ 表达式开头、结尾或表达式内部可能有多余的空格。

(1) 模拟

设两个栈，一个是操作数栈，用来存放操作数，如 3、4、8 等，另一个是运算符栈，用来存放运算符。
首先，将“(”压进运算符栈的栈底①。然后，依次扫描，按照栈的后进先出原则进行：
① 遇到操作数，进操作数栈；
② 遇到运算符时，则需将此运算符的优先级与栈顶运算符的优先级比较。
若高于栈顶元素则进栈，继续扫描下一符号。否则，将运算符栈的栈顶元素退栈，形成一个操作码 Q，同时操作数栈的栈顶元素两次退栈，形成两个操作数 a、b，让计算机对操作数与操作码完成一次运算操作，即 aQb，并将其运算结果存放在操作数栈中。
注意：在向 calc 函数传入表达式之前，必须在表达式两端加一层小括号！

#define Pop { pos--; \
switch (symbol[pos+1]) { \
case '+': number[pos]+=number[pos+1];break; \
case '-': number[pos]-=number[pos+1];break; \
case '*': number[pos]*=number[pos+1];break; \
case '/': number[pos]/=number[pos+1];break; \
case '^': number[pos]=pow(number[pos],number[pos+1]);break;\
}; \
}
#define Push symbol[++pos]=exp[i];
#define SkipBlank { while(c==' ') i++; } // 跳过空白
#define Is_it(x,a,b) (x==a||x==b) // 判断x是否为a或b
#define Is_them(x,a,b,c,d) (x==a||x==b||x==c||x==d) // 判断x是否为a、b、c、d之一
int number[1000]; // 操作数栈
char symbol[1000]; // 运算符栈
int pos;
int pow(int, int); // 乘方运算的代码见37页"4.3 快速幂!"。
int val(char *s, int &i) // 字母变数字
{
int n=0;
while (s[i]>='0' && s[i]<='9')
{
n=n*10+(s[i]-'0');
i++;
}
return n;
}
#define c exp[i]
int calc(char *exp, int n)
{
pos=number[0]=0;
int i=0;
char t;
while (i<=n)
{
SkipBlank
while (c=='(') // 处理左括号
{
SkipBlank
Push
i++;
}
SkipBlank
number[pos]=val(exp,i);
SkipBlank
do
{
if (c==')') // 处理右括号
{
while (symbol[pos]!='(')
Pop
pos--;
number[pos]=number[pos+1];
} else {
while (true) // 运算符入栈或出栈处理
{
if (Is_it(c,'+','-') && symbol[pos]!='(')
Pop
else if (Is_it(c,'*','/') && Is_it(symbol[pos],'*','/'))
Pop
else if (Is_them(c,'+','-','*','/') && symbol[pos]=='^')
Pop
else
break;
}
SkipBlank
Push
}
t=exp[i]; // 接下来可能会遇到空格。如果不这样，会出错的。
i++;
SkipBlank
} while (i<=n && t==')');
}
return number[0];
}

(2) 分治

找出式中最后运算的运算符 A，先递归地求出其左右两边的值，再将得到的值进行 A 运算。

int pow(int, int); // 乘方运算的代码见128页“11.8 快速幂!”。
int str2int(char *s, int x, int y) // 字符串变数字
{
int n=0;
for (int i=x; i<=y; i++)
if (s[i]>='0' && s[i]<='9')
n=n*10+(s[i]-'0');
else if (s[i]!=' ')
break;
return n;
}
int calc(char *exp, int x, int y)
{
int lv=0, p=-1;
// 去除两端空格
while (exp[x]==' ' && x<=y) x++;
while (exp[y]==' ' && x<=y) y--;
for (int i=x; i<=y; i++)
{
char &c = exp[i];
if (c==' ') continue;
if (c=='(') lv++;
if (c==')') lv--;
if (lv==0)
{
// 当出现优先级运算时，采取优先级较低的运算符；优先级相同时，采取靠后的运算符。
if (Is_it(c,'+','-'))
p=i;
else if (Is_it(c,'*','/') && (p==-1 || !Is_it(exp[p],'+','-')))
p=i;
else if (p==-1 && c=='^')
p=i;
}
}
if (p==-1)
{
// 去除两端括号
if (exp[x]=='(' && exp[y]==')') return calc(exp, x+1, y-1);
if (exp[x]=='(') return calc(exp, x+1, y);
if (exp[y]==')') return calc(exp, x, y-1);
// 字符变数字
return str2int(exp, x, y);
} else {
int a=calc(exp, x, p-1);
int b=calc(exp, p+1, y);
switch (exp[p])
{
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
case '^': return pow(a,b);
};
}
return 0;
}

(3) 表达式树
用分治和递归的思想构建表达式树。对树进行一次遍历，边遍历边计算，就可以算出表达式的值。
对表达式树进行前序遍历、中序遍历和后序遍历，分别会得到前缀表达式、中缀表达式和后缀表达式。其中后缀表达式不需要括号。以下图为例，三种表达式分别为：
前缀表达式：- + 3 * 7 - 3 2 / 4 2

中缀表达式：3 + 7 * 3 - 2 - 4 / 2

后缀表达式：3 7 3 2 - * + 4 / 2 –