华为上机测试题2011

简单四则运算

问题描述：
输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值
注：
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;
}