华为上机测试题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;elseleft = pre->d1 - '0';if (rear->d1 == '@')right = rear->d2;elseright = 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;}