华为上机测试题2011

婵娟9428

简单四则运算
问题描述：
输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值
注：
1、表达式只含 +, -, *, / 四则运算符，不含括号
2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况
3、要考虑加减乘除按通常四则运算规定的计算优先级
4、除法用整数除法，即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生
5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况
代码实现：
#include <stdio.h>
#include <stdlib.h>
// 1.使用链表实现，先定义链表
struct node
{
char d1;     // 存放字符，若为 @ 说明 d2 有效
int  d2;     // 存放经过运算的结果，一个字符不足以保存结果
struct node* next;
};
typedef struct node *pnode;
typedef pnode mylist;
// 2.实现字符串到链表的转换
mylist create(char str[])
{
pnode head,tmp;
head = tmp = (pnode)malloc(sizeof(struct node));
head ->d1 = str[0];
head ->d2 = -1;
while(*(++str) != '\0')
{
tmp->next = (pnode)malloc(sizeof(struct node));
tmp = tmp->next;
tmp->d1 = *str;
tmp->d2 = -1;
}
tmp->next = NULL;
return head;
}
// 3.实现运算合并节点，例如 "7*2" 合并为 "14"
void merge(pnode loc,char sym)
{
int ans,left,right;
pnode pre,cur,rear;
pre = loc;
cur = pre ->next;
rear = cur ->next;
if (pre->d1 == '@')
left = pre->d2;
else
left = pre->d1 - '0';
if (rear->d1 == '@')
right = rear->d2;
else
right = rear->d1 - '0';
switch(sym)
{
case '+':
ans = left + right;
break;
case '-':
ans = left - right;
break;
case '*':
ans = left * right;
break;
case '/':
ans = left / right;
break;
default:
break;
}
pre->d1 = '@';
pre->d2 = ans;
pre->next = rear->next;
free(cur);
free(rear);
}
// 4.主要计算函数，若有字符串"8+7*2-9/3"，计算出其值为19。
int calculate(int len,char *expStr)
{
mylist ml = create(expStr);
// a.扫描找到 */ 的位置,计算
pnode tmp,rear;
rear = ml;
while (rear != NULL)
{
char sym = (char)(rear->d1);
if (sym == '*' || sym == '/')
{
merge(tmp,sym);
rear = tmp;
}
tmp = rear;
rear = rear->next;
}
// b.扫描找到 +- 的位置,计算
rear = ml;
while (rear != NULL)
{
char sym = (char)(rear->d1);
if (sym == '+' || sym == '-')
{
merge(tmp,sym);
rear = tmp;
}
tmp = rear;
rear = rear->next;
}
return ml->d2;
}
int main(int argc, char* argv[])
{
char str[] = "8+7*2-9/3";
printf("%d\n",calculate(strlen(str),str));
system("pause");
return 0;
}