Posted on 2010-09-03 21:53
acronix 阅读(438)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：求算术表达式。
分析：表达式有中缀转化为后缀。设一个stack存后缀数据，一个rout栈存运算符。
方法：（1）从右向左依次取得数据ch。
（2）如果ch是操作数，直接加进stack中。
（3）如果ch是运算符（含左右括号），则：
a：如果ch = '('，放入堆栈rout中。
b：如果ch = ')'，依次输出堆栈rout中的运算符，直到遇到'('为止。
c：如果ch不是')'或者'('，那么就和堆栈rout顶点位置的运算符top做优先级比较。
1：如果ch优先级比rtop高，那么将ch放入堆栈。
2：如果ch优先级低于或者等于rtop，那么输出top到stack中（直到！top或者满足 1），然后将ch放入堆栈。
注：运算符的优先级：^ , *、/，%，+ -，注意本题多个乘方如2^(-1)^2^2是左结合，而我比赛的时用的是右结合，还有就是查了很多文档，很多都是右结合，所以暂时还没弄清。不过本题考查的重点还是栈的使用和中缀转后缀表达式或者用表达树。
cpp代码：
#include <cstdio>
#include <ctype.h>
#include <cmath>
#include <stdlib.h>
char rin[10100],rout[10100];
struct sta{
double x;
bool digit;
char ch;
} stack[10100];
double tst[10100];
int top,ttop,rtop;
int priority(char ch)
{
switch (ch)
{
case '+' :
case '-' : return 1;break;
case '*' :
case '/' : return 2;break;
case '^' : return 3;break;
}
}
int main()
{
// freopen("Lazy.in","r",stdin);
// freopen("out.txt","w",stdout);
int i;
bool mark;
while (scanf("%s",rin) != EOF)
{
mark = true;
top = 0; i = 0; rtop = 0;
while (rin[i])
{
if (mark)
{
mark = false;
while (rin[i] == '(')
{
i ++;
rout[++rtop] = '(';
}
if (rin[i] == '-' || rin[i] == '+')
{
stack[++top].x = 0;
stack[top].digit = true;
}
else {
sscanf(&rin[i],"%lf",&stack[++top].x);
stack[top].digit = true;
while (!isdigit(rin[i]))
i++;
while (isdigit(rin[i]) || rin[i] == '.')
i++;
}
}
else {
mark = true;
if (rin[i] == ')')
{
while (rout[rtop] != '(')
{
stack[++top].ch = rout[rtop--];
stack[top].digit = false;
}
rtop--;
mark = false;
}
else {
if (!rtop || rout[rtop] == '(')
rout[++rtop] = rin[i];
else {
while ( rtop&& priority(rin[i]) < priority(rout[rtop]))
{
stack[++top].ch = rout[rtop--];
stack[top].digit = false;
}
if (rtop && priority(rin[i]) == priority(rout[rtop]))
{
stack[++top].ch = rout[rtop];
stack[top].digit = false;
rout[rtop] = rin[i];
}
else rout[++rtop] = rin[i];
}
}
i ++;
}
}
while (rtop)
{
stack[++top].ch = rout[rtop--];
stack[top].digit = false;
}
/* for (i = 1;i <= top; i++)
{
if (stack[i].digit)
printf("%.0lf\n",stack[i].x);
else printf("%c\n",stack[i].ch);
}*/
ttop = 0; i = 1;
bool flag = true;
while (i <= top && flag)
{
if (stack[i].digit)
tst[++ttop] = stack[i].x;
else {
double b = tst[ttop--], a = tst[ttop];
switch (stack[i].ch)
{
case '+': tst[ttop] = a + b;
break;
case '-': tst[ttop] = a - b;
break;
case '*': tst[ttop] = a * b;
break;
case '/': if (fabs(b) < 0.00000001)
flag = false;
else tst[ttop] = a / b;
break;
case '^': tst[ttop] = pow(a,b);
break;
}
}
i++;
}
if (flag)
printf("%.8lf\n",tst[ttop]);
else printf("The teacher is so lazy!\n");
}
return 0;
}