表达式求值（整数运算）

#include <cstdio>
#include <map>
#include <malloc.h>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))

map<char,int> d;		//字符到数字的映射，比较大小用 

int cmp[7][7] =		//优先级比较，1为大于，0为等于，-1为小于。-2为空 
{
	{1,1,-1,-1,-1,1,1},
	{1,1,-1,-1,-1,1,1},
	{1,1,1,1,-1,1,1},
	{1,1,1,1,-1,1,1},
	{-1,-1,-1,-1,-1,0,-2},		//这里最后一个元素为空，因为(不可能与#比较 
	{1,1,1,1,-2,1,1},
	{-1,-1,-1,-1,-1,-2,0}
};

typedef struct data
{
	char op;		//运算符
	int num;		//数字 
}data;

typedef struct StackNode		//链栈 
{
	data e;
	StackNode *next;
}StackNode,*LinkStack;

void StackInit(LinkStack &s)		//初始化栈 
{
	s = (StackNode *)malloc(sizeof(StackNode));
	s = NULL;
}

void WelCome()
{
	d['+'] = 0;
	d['-'] = 1;
	d['*'] = 2;
	d['/'] = 3;
	d['('] = 4;
	d[')'] = 5;
	d['#'] = 6;
	//以上为字符的数字化 
	printf ("\n\n");
	printf ("******************************************************************\n");
	puts("\t欢迎使用表达式求值程序！");
	puts("\t表达式以#开始并以#结束");
	puts("\t注意：请输入正确的表达式，此程序并无判错机制。");
	printf ("******************************************************************\n\n");
}

void StackPush(LinkStack &s,data a)		//压入栈 
{
	LinkStack p;
	p = (StackNode *)malloc(sizeof(StackNode));
	p->e = a;
	p->next = s;
	s = p;
}

bool IsNum(char ch)		//判断是否为数字 
{
	return (ch >= '0' && ch <= '9') ? true : false;
}

void StackTop(LinkStack s,data &t)		//取栈顶元素 
{
	t = s->e;
}

void StackPop(LinkStack &s)		//弹出栈顶元素 
{
	LinkStack p;
	p = s;
	s = s->next;
	free(p);
}

void StackClear(LinkStack s)
{
	if (s == NULL)
		return;
	StackClear(s->next);
	free(s);
}

int Cal(int a,int b,char op)
{
	switch(op)
	{
		case '+':
			return a+b;
		case '-':
			return b-a;
		case '*':
			return a*b;
		case '/':
			return b/a;
	}
}

void solve(char *str)		//计算表达式 
{
	int l = strlen(str);
	char ch;
	int a,b,c;
	LinkStack sop;
	LinkStack snum;
	StackInit(sop);
	StackInit(snum);
	data t;
	t.op = '#';
	StackPush(sop,t);
	for (int i = 1 ; i < l ; i++)
	{
		ch = str[i];
		if (IsNum(ch))
		{
			int num = 0;
			while (IsNum(ch))		//依次读数存入t中 
			{
				num = num * 10 + ch - '0';
				ch = str[++i];
			}
			i--;		//返回最后一个数字
			t.num = num;
			StackPush(snum,t);		//把数字压入栈 
		}
		else
		{
			data top_op;
			data top_num;
			StackTop(sop,top_op);
			switch(cmp[d[top_op.op]][d[ch]])
			{
				case -1:
					t.op = ch;
					StackPush(sop,t);
					break;
				case 1:
					StackTop(snum,top_num);
					a = top_num.num;
					StackPop(snum);
					StackTop(snum,top_num);
					b = top_num.num;
					StackPop(snum);
					//取两次栈顶数字 
					StackTop(sop,top_op);
					StackPop(sop);			//取栈顶运算符  
					c = Cal(a,b,top_op.op);		//计算一次结果 
					t.num = c;
					StackPush(snum,t);		//以string型存入数字栈 
					i--;
					break;
				case 0:
					StackPop(sop);
					break;
			}
		}
	}
	StackTop(snum,t);
	cout << t.num << endl;
	StackClear(sop);
	StackClear(snum);
}

int main()
{
	char str[100];
	WelCome();
	puts("请输入的表达式：");
	int ans;
	while (scanf ("%s",str))
	{
		if (str[0] != '#' || (str[0] == '#' && str[1] == '#'))
		{
			puts("\n谢谢您的使用！请按任意键退出!");
			system("pause");
			break;
		}
		solve(str);
		printf ("请输入的表达式：\n");
	}
	return 0;
}