算法思路
? 上次已经完成了由中缀表达式转后缀表达式的算法,而后缀表达式的优点就是可以从左至右直接读取,没有算数优先级的考量,所以直接进行运算即可。
? 该算法需要使用一个栈用来保存操作数,在读取到数字的时候,将数字压入栈中;如果读取到操作符,就弹出栈顶的两个元素,分别为op2和op1(先弹出来的元素为op2),将op1和op2与目前读取到的操作符进行计算,并将结果压回栈中。反复运行直到后缀表达式全部读取完成,此时栈中的结果即后缀表达式的结果。
具体过程
例后缀表达式12+3-45*2/+ ,定义一个栈num 来保存数字,顺序读取后缀表达式。
- 读取到数字
1 ,将其压入栈中,此时num = ['1'] - 读取到数字
2 ,将其压入栈中,此时num = ['1','2'] - 读取到操作符
+ ,将栈顶的两个元素弹出,op2=2 ,op1=1 ,将op1+op2 的结果压入栈中,此时num = ['3'] - 读取到数字
3 ,将其压入栈中,此时num = ['3','3'] - 读取到操作符
- ,将栈顶的两个元素弹出,op2=3 ,op1=3 ,将op1-op2 的结果压入栈中,此时num = ['0'] - 读取到数字
4 ,将其压入栈中,此时num = ['0','4'] - 读取到数字
5 ,将其压入栈中,此时num = ['0','4','5'] - 读取到操作符
* ,将栈顶的两个元素弹出,op2=5 ,op1=4 ,将op1*op2 的结果压入栈中,此时num = ['0','20'] - 读取到数字
2 ,将其压入栈中,此时num = ['0','20','2'] - 读取到操作符
/ ,将栈顶的两个元素弹出,op2=2 ,op1=20 ,将op1/op2 的结果压入栈中,此时num = ['0','10'] - 读取到操作符
+ ,将栈顶的两个元素弹出,op2=10 ,op1=0 ,将op1+op2 的结果压入栈中,此时num = ['10'] - 后缀表达式读取完毕,此时栈
num 的内容即后缀表达式的结果。
代码实现
void postfixEval()
{
char postfixList[100] = {0};
printf("请输入将要求值的后缀表达式:\n");
scanf("%s", postfixList);
getchar();
int length;
length = (int) strlen(postfixList);
LiStack num;
num = initStack();
for (int i = 0; i < length; i++)
{
if (isdigit(postfixList[i]))
{
int nums = asciiToint(postfixList[i]);
push(num, nums);
}
else
{
int second = pop(num);
int first = pop(num);
push(num, domatch(first, postfixList[i], second));
}
}
printf("该表达式的值为%d\n", pop(num));
}
int asciiToint(char ascii)
{
int i = ascii - '0';
return i;
}
int domatch(int op1, char op, int op2)
{
int first = (int)op1, second = (int)op2;
if (op == '*')
{
return first * second;
}
else if(op == '/')
{
return first / second;
}
else if (op == '+')
{
return first + second;
}
else
{
return first - second;
}
}
|