转发个严蔚敏老师的《数据结构及应用算法教程》里的十进制四则运算计算器代码，实习生笔试遇到过不会写，特此做个记录。
**************************
文件：calculator.c
**************************
#define NonEmpty 0
#define PLUS -1 // '+'#define MINUS -2 // '-'#define ASTERISK -3 // '*' #define SLANT -4 // '/'#define MAX_EXP_LENGTH 50 // 表达式最大长度#define MAX_OPERAND 10 // 操作数最大长度#include"ExpBinTree.h"
void main()
{ cout<<"EXAMPLE: -(a-b)/((c+d)*e)+f-g#"<<endl; cout<<"AT THE END OF EXPRESSION, PLEASE ADD '#'"<<endl;char exp[MAX_EXP_LENGTH]; // 输入表达式缓存数组
BiTree T; OElemType operand[MAX_EXP_LENGTH/2]; // 定义数组operand存放每个操作数 char *operate = "/+-*#()"; // 定义数组operate建立操作符集合cout<<endl<<"INUPT: ";
GetExp(exp); CrtExptree(T, exp, operand, operate); // 调用函数CrtExptree,建立二叉树 // 调用函数Value ,计算结果 cout<<"value= "<<Value(T,operand)<<endl;}**************************
文件：COMMON.h
**************************
#include<iostream.h>
#include<iomanip.h>#include<stdlib.h>#include<process.h>#include<string.h>#define TRUE 1
#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1
#define OVERFLOW -2#define MAXINT 30000
typedef int status;**************************
文件：ExpBinTree.h
**************************
typedef int TElemType; // 树结点数据域类型为整型
typedef float OElemType; // 操作数类型为浮点型typedef struct BiTNode{ // 二叉树的类型定义
TElemType data; struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;typedef union {
char OPTR; // SElemType 可以字符也可以是 二叉树的结点 BiTree BiT; } SElemType;#include"stack.h"
/************************* 出错信息处理函数定义 ***********************/
void ERRORMESSAGE(char *s) { cout<<s<<endl; exit(1);} //ERRORMESSAGE/*************************** 输入数据的操作 ***********************/
void GetExp(char *Exp){//得到一个表达式,并对其进行单目运算的模式匹配 char ch; int n=FALSE, i=0; do { cin>>ch; if (n==TRUE && (ch=='-' || ch=='+')) Exp[i++]='0'; else n=FALSE; Exp[i++]=ch; if (ch=='(') n=TRUE; } while (ch!='#'); Exp[i]='\0';}//GetExp/********************表达式树的相关操作 *******************/status IN(char ch,char *OP)
{ //判断字符ch 是否属于运算符集 char *p=OP; while (*p && ch!=*p ) ++p; if (!*p) return ERROR; return OK;}//IN void ChangeOPND( char *p ,int pos, int &n, OElemType *operand){ //把相应的字符串转成对应的运算数,并存入operand数组中,pos是operand中的位序 //使用 atof 系统函数进行转换. char data[MAX_OPERAND], *q = data; n=0; while ((*p<='9' && *p>='0') || (*p=='.')) { *q++=*p++; n++; } *q = '\0'; operand[pos] = (float)atof(data);}//ChangeOPNDvoid CrtNode(BiTree &T,int position ,Stack &PTR)
{ // 建叶子结点^T, 结点中的数据项为操作数所在的operand数组中的位置 // 建立完成后把结点装入PTR栈 SElemType e; T = new BiTNode; T->data = position; T->lchild = T->rchild = NULL; e.BiT = T; Push(PTR, e);}//CrtNodeint ChangeOPTR(char ch)
{ // 把相应的操作符转成宏定义值 int n; if (ch=='+') n = PLUS; else if (ch=='-') n = MINUS; else if(ch=='*') n = ASTERISK; else if(ch=='/') n = SLANT; return n;}//ChangeOPTRvoid CrtSubtree (BiTree &T, char ch, Stack &PTR)
{ // 建子树^T, 其中根结点的数据项为操作符 SElemType e; T = new BiTNode; T->data = ChangeOPTR(ch); if (Pop(PTR, e)) T->rchild = e.BiT; else T->rchild = NULL; if (Pop(PTR, e)) T->lchild = e.BiT; else T->lchild = NULL; e.BiT = T; Push(PTR, e);}//CrtSubtreestatus precede(char c,char ch)
{ //算符间的优先关系表,此表表示两操作符之间的大于小于关系 switch (c) { case '#': case '(': return ERROR; case '*': case '/': case '+': case '-': if (!(ch!='*' && ch!='/')) return ERROR; return OK; default : return OK; }}//precedevoid CrtExptree(BiTree &t, char *exp, OElemType *operand, char *operate)
{ // 建立由合法的表达式字符串确定的只含二元操作符的 // 非空表达式树，其存储结构为二叉链表SElemType e,c;
char *p,ch; int pos=0,n; Stack S_OPTR,S_BiT; // 栈S_OPTR内放表达式的操作符,栈S_BiT放生成的结点 InitStack(S_OPTR); e.OPTR = '#'; Push(S_OPTR,e); // 把字符#进栈 InitStack(S_BiT); p = exp; ch = *p; // 指针p指向表达式 GetTop(S_OPTR,e); while (!(e.OPTR=='#' && ch=='#')) // 当从栈S_OPTR退出的操作符为#,且ch=='#'时循环结束 { if (!IN(ch,operate)) // 判断ch 是否属于操作符集合operate, { ChangeOPND(p,pos,n,operand); // 如果不属于操作符,把其转成操作数 p+=(n-1); // 移动字符串指针 CrtNode( t,pos++, S_BiT); // 建叶子结点 } else { switch (ch) // 如果属于操作符 { case '(' : e.OPTR = ch; Push(S_OPTR, e); // 左括号先进栈 break; case ')' : { // 脱括号创建子树 Pop(S_OPTR, c); while (c.OPTR!= '(' ) { CrtSubtree( t, c.OPTR,S_BiT); Pop(S_OPTR, c); } break; } default : { while(GetTop(S_OPTR, c) && (precede(c.OPTR,ch))) // 栈顶元素优先权高 { CrtSubtree( t, c.OPTR, S_BiT); // 建子树. Pop(S_OPTR, c); } if (ch!= '#') { e.OPTR = ch; Push( S_OPTR, e); // 如果ch不为#,让ch进栈 } break; } // default } // switch } // else if ( ch!= '#' ) { p++; ch = *p;} // 如果ch不为#,p指针后移 GetTop(S_OPTR,e); } // while e.BiT = t; Pop(S_BiT, e);} // CrtExptreeOElemType Value(BiTree T, OElemType *operand)
{ // 递归求值,使用后序遍历,operand数组存放叶子结点的数值 OElemType lv,rv,v; if (!T) return 0; if (!T->lchild && !T->rchild) return operand[T->data]; lv = Value(T->lchild,operand); rv = Value(T->rchild,operand); switch (T->data) { case PLUS: v = lv+rv; break; case MINUS: v = lv-rv; break; case ASTERISK: v = lv*rv; break; case SLANT: if (rv==0) ERRORMESSAGE("ERROR"); // 除法运算分母不能为零 v = lv/rv; break; } return v;}//Value**************************
文件：STACK.h
**************************
#include "common.h"
#define STACK_INIT_SIZE 100//定义栈的初始长度#define STACKINCREMENT 10 //定义栈每次追加分配的长度//实现栈的数据类型typedef struct{
SElemType *elem; int top; int stacksize; }Stack;//栈的各项操作的实现status InitStack(Stack &s){ //初始化栈 s.elem=new SElemType[STACK_INIT_SIZE]; if (!s.elem) return OVERFLOW; s.top=-1; s.stacksize=STACK_INIT_SIZE; return OK; }status DestroyStack(Stack &s){ //销毁栈 delete s.elem; s.top=-1;s.stacksize=0; return OK; }status ClearStack(Stack &s){ //当栈存在时将栈清空 //当栈不存在时返回出错信息 if (!s.elem) return ERROR; s.top=-1; return OK; }status StackEmpty(Stack &s){ //判断栈空与否，空时返回TRUE，否则返回ERROR. //当栈不存在时返回出错信息 if (!s.elem) return ERROR; if (s.top<0) return TRUE; return FALSE; }int StackLength(Stack s){ //返回栈的长度 //当栈不存在时返回出错信息 if (!s.elem) return ERROR; return s.top+1; }status GetTop(Stack s,SElemType &e){ //当栈存在且不空时返回栈顶元素 //当栈不存在或栈空时返回出错信息 if (!s.elem) return ERROR; if (s.top<0) return ERROR; e=s.elem[s.top]; return OK; }status Push(Stack &s,SElemType e){ //当栈存在时压栈 //当栈不存在时返回出错信息 if (!s.elem) return ERROR; if ((s.top+1)==s.stacksize){ //当栈的初始空间已满 SElemType *temp=s.elem; int i; //为栈重新分配存储空间 s.stacksize+=STACKINCREMENT; s.elem=new SElemType[s.stacksize]; if (!s.elem) return OVERFLOW; //当分配失败时返回出错信息 for(i=0;i<=s.top;i++) s.elem[i]=temp[i]; delete temp; }// if s.top+=1; s.elem[s.top]=e; return OK; }status Pop(Stack &s,SElemType &e){ //当栈存在且不空时退栈 //当栈不存在或栈空时返回出错信息 if(!s.elem) return ERROR; if(s.top<0) return ERROR; e=s.elem[s.top]; s.top-=1; return OK; }status StackTraverse(Stack s,int (*visit)(SElemType &e)){ //当栈存在且不空时调用visit函数对栈作由底到头的遍历 //当visit函数调用失败返回错误信息 //当栈不存在或栈空时返回出错信息 int i; if (!s.elem) return ERROR; if (s.top<0) return ERROR; for(i=0;i<=s.top;i++) visit(s.elem[i]); return OK; }