前缀式计算
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
先说明一下什么是中缀式：
如2+(3+4)*5这种我们最常见的式子就是中缀式。
而把中缀式按运算顺序加上括号就是：(2+((3+4)*5))
然后把运算符写到括号前面就是+(2 *( +(3 4) 5) )
把括号去掉就是：+ 2 * + 3 4 5
最后这个式子就是该表达式的前缀表示。
给你一个前缀表达式，请你计算出该前缀式的值。
比如：
+ 2 * + 3 4 5的值就是 37
- 输入
- 有多组测试数据，每组测试数据占一行，任意两个操作符之间，任意两个操作数之间，操作数与操作符之间都有一个空格。输入的两个操作数可能是小数，数据保证输入的数都是正数，并且都小于10，操作数数目不超过500。
以EOF为输入结束的标志。 - 输出
- 对每组数据，输出该前缀表达式的值。输出结果保留两位小数。
- 样例输入
+ 2 * + 3 4 5
+ 5.1 / 3 7- 样例输出
- 37.00
- 5.53
这个题目也是用栈来做的，只不过顺序与后缀式有点不同,他与中缀的区别是可以不用比较优先级，
因为前缀和后缀式中都没有括号，直接按照顺序计算就行了，下面是具体的实现代码，代码中有注释，
如有不懂的，可以留言…
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
typedef struct stack{
double data;
struct stack *next;
}stack;
stack *init();
int isOperand(char ch);
stack *push_stack(stack *top, double data);
stack *pop_stack(stack *top);
void calc(stack **top, char ch);
int main()
{
char ch[], temp[];
stack *top;
top = init();
double num; int i, count, flag, j;
while(gets(ch) != NULL)
{
i = strlen(ch) - ;
while(i >= )
{
if(ch[i] == ' ')//判断如果是空格，继续下一个
{
i --;
continue;
}
if(isOperand(ch[i]))//如果是运算符，这是调用计算函数
{
calc(&top, ch[i]);
i --;
continue;
}
count = ; flag = ; j = ;
while(!isOperand(ch[i]) && ch[i] != ' ' && i >= )//判断是数字的话就保存到一个新的数组中
{
temp[j++] = ch[i];
i --;
}
j = j -;
num = ;
while(j >= )//将字符串解析成double类型数字
{ if(temp[j] == '.')
{
flag = ;
j --;
continue;
}
if(flag)
num = num * + (temp[j] - '');//如果没出现小数点之前，都是*10 + 本身的
else
{
count ++;
num += pow(0.1, count) * (temp[j] - '');//出现小数点之后就得加上0.1的count此方了
}
j --;
}
top = push_stack(top, num);
}
printf("%.2f\n", top -> data);
}
return ;
}
stack *init()//初始化栈
{
stack * node;
node = (stack *)malloc(sizeof(stack));
node -> next = NULL;
return node;
}
int isOperand(char ch)//判断是不是运算符
{
if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
return ;
return ;
}
stack *push_stack(stack *top, double data)//入栈
{
stack *node;
node = init();
node -> data = data;
node -> next = top;
top = node;
return top;
}
stack *pop_stack(stack *top)//出栈
{
stack *node;
node = top;
top = top -> next;
free(node);
return top;
}
void calc(stack **top, char ch)//计算函数，当然也可以不用二级指针，把void改成stack返回类型 就行了
{
double num1, num2;
num1 = (*top) -> data;
(*top) = pop_stack(*top);
num2 = (*top) -> data;
(*top) = pop_stack(*top);
switch(ch)
{
case '+':
num1 = num1 + num2;
break;
case '-':
num1 = num1 - num2;
break;
case '*':
num1 = num1 * num2;
break;
case '/':
num1 = num1 / num2;
break;
}
(*top) = push_stack(*top, num1);//计算完之后将结果继续入栈
}