(C语言版)科学计算器设计.doc

科学计算器设计(C语言版)
学校：
学院：计算机信息工程学院
语言
平台：
作者：
日期：

一、 背景和目的
计算器是现代日常生活中使用较为频繁的工具之一，常用的计算器有简易版和科学计算器两种模式。简易版的计算器不支持表达式运算，每次只能输入一个数据或者运算符来计算，而科学计算器除了容纳简易版计算器的功能外，还支持表达式运算，用户可以输入一个合法的算术表达式来得到所需的结果。
常用的算术表达式有三种，前缀表达式，中缀表达式和后缀表达式。
中缀表达式：我们平时书写的表达式就是中缀表达式，形如（a+b）*（c+d），事实上是运算表达式形成的树的中序遍历，特点是用括号来描述优先级。
后缀表达式：也叫逆波兰表达式，事实上是算数表达式形成的树的后序遍历。中缀表达式（a+b）*（c+d）的后缀表达式是ab+cd+*，它的特点就是遇到运算符就立刻进行运算。
前缀表达式：算数表达式形成的树的前序遍历。
日常所书写的是中缀表达式，但是计算机内部是用后缀表达式计算，所以此程序的用户使用中缀表达式作为输入，程序将中缀表达式转化为后缀表达式后再进行运算并输出结果。
由于今后工作将使用C语言进行开发，而C语言是一个功能强大并且很灵活的语言，为复习和巩固C编程，故决定用C语言编写一个科学计算器。
本次开发采用C语言，以面对过程思想进行开发，使用的数据结构有队列和栈。

二、 模块设计
本次开发，使用的控制台输入，并直接在控制台输出。
科学计算器的功能组件如下：
中缀表达式转后缀表达式
trans_expr()
输入表达式
input_expr ()
当读到数字直接送至输出队列中
当读到运算符T时
a：将栈中所有优先级高于或等于T的运算符弹出，送至输出队列
b：T进栈
读到左括号时总是将它压入栈中
读到右括号时，将靠近栈顶的第一个左括号上面的运算符依次全部弹出，送至输出队列，再丢弃左括号
计算后缀表达式
calcu_expr()
建立一个栈
从左到右读后缀表达式，读到数字就将它压入栈S中，读到运算符则从栈中依次弹出两个数X和Y，然后以“X运算符Y”的形式计算出结果，再将结果压入栈S

如果后缀表达式未读完，就重复上述过程，最后输出栈顶数值则为结束
输出结果
转换成功
Y
N

三、 详细设计
宏：
#define TEST //表示测试阶段
#define MAX_SIZE 100 //表达式长度
#define LBRACKET 0 //左括号
#define RBRACKET 1 //右括号
#define ADD 2 //加
#define SUB 3 //减
#define MUL 4 //乘
#define DIV 5 //乘
#define INT 6 //整数
#define DOUBLE 7 //浮点数

数据结构:
表达式节点
struct ExprNode{
int n; //表达式节点类型
double p; //表达式节点数据
};

中缀表达式：
struct ExprNode infixExpr[MAX_SIZE];
int infixLen;

后缀表达式：
struct ExprNode suffixExpr[MAX_SIZE];
int suffixLen;

后缀转换栈：
int transStack[MAX_SIZE];
int transTop;

后缀表达式运算栈：
struct ExprNode calcuStack[MAX_SIZE];
int calcuTop;

函数过程：
__inline int get_char( char *c )
缓冲变量无字符则读入字符
读入成功返回0,否者返回-1

int input_expr( void )
读入表达式
若输入非法字符则返回-1，否则返回0

int pri( int a, int b )
优先级计算
若a优先于b则返回-1,否则返回0

int trans_expr( void )
中缀表达式转换为后缀表达式
括号不匹配返回-1,否则返回0

__inline int maxn( int a, int b )
求最大值

struct ExprNode calcu( struct ExprNode *a, struct ExprNode *b, int c )
计算a和b做c运算的结果

int calcu_expr( void )
计算后缀表达式
表达式计算失败返回-1,否则为0

void show( void )
输出运算结果

代码：
#include<stdio.h>

//#define TEST //表示测试阶段
#define MAX_SIZE 100 //表达式长度
#define LBRACKET 0 //左括号
#define RBRACKET 1 //右括号
#define ADD 2 //加
#define SUB 3 //减
#define MUL 4 //乘
#define DIV 5 //乘
#define INT 6 //整数
#define DOUBLE 7 //浮点数

struct ExprNode{
int n; //表达式节点类型
double p; //表达式节点数据
};
struct ExprNode infixExpr[MAX_SIZE]; //中缀表达式
int infixLen;
struct ExprNode suffixExpr[MAX_SIZE]; //后缀表达式
int suffixLen;

int transStack[MAX_SIZE]; //后缀转换栈
int transTop;

struct ExprNode calcuStack[MAX_SIZE]; //后缀表达式运算栈
int calcuTop;

//缓冲变量无字符则读入字符
//读入成功返回0,否者返回-1
__inline int get_char( char *c )
{
if ( *c == '\0' ) return scanf( "%c", c );
return 0;
}

//读入表达式
//若输入非法字符则返回-1，否则返回0
int input_expr( void )
{
char c = 0;
int flag = 0, error = 0, s, i;
infixLen = 0;
while ( get_char(&c) != -1 )
{
switch ( c )
{
case '\n': flag = -1; break;
case '(': infixExpr[infixLen++].n = LBRACKET; c = 0; break;
case ')': infixExpr[infixLen++].n = RBRACKET; c = 0; break;
case '+': infixExpr[infixLen++].n = ADD; c = 0; break;
case '-': infixExpr[infixLen++].n = SUB; c = 0; break;
case '*': infixExpr[infixLen++].n = MUL; c = 0; break;
case '/': infixExpr[infixLen++].n = DIV; c = 0; break;
default:
if ( c >= '0' && c <= '9' || c == '.' )
{
if ( c != '.' )
{
infixExpr[infixLen].n = INT;
infixExpr[infixLen].p = c-'0';
s = 0;
}
else
{
infixExpr[infixLen].n = DOUBLE;
infixExpr[infixLen].p = 0;
s = 1;
}
c = 0;
while ( get_char(&c) != -1 )
{
if ( c >= '0' && c <= '9' )
{
infixExpr[infixLen].p = infixExpr[infixLen].p*10+(c-'0');
if ( s ) s++;
c = 0;
}
else if ( c == '.' )
{
if ( s )
{
error = -1;
}
else
{
infixExpr[infixLen].n = DOUBLE;
s++;
}
c = 0;
}
else break;
}
if ( infixExpr[infixLen].n == DOUBLE )
{
for ( i = 1; i < s; i++ )
{
infixExpr[infixLen].p /= 10;
}
}
infixLen++;
}
else
{
error = -1;
c = 0;
}
break;
}
if ( flag ) break;
};
return error;
}

//优先级计算
//若a优先于b则返回-1,否则返回0
int pri( int a, int b )
{
int c[2], p[2], i;
c[0] = a; c[1] = b;
for ( i =0; i < 2; i++ )
{
switch ( c[i] )
{
case LBRACKET: p[i] = 0; break;
case ADD:
case SUB: p[i] = 1; break;
case MUL:
case DIV: p[i] = 2; break;

}
}
if ( p[0] >= p[1] )
{
return -1;
}
return 0;
}

//中缀表达式转换为后缀表达式
//括号不匹配返回-1,否则返回0
int trans_expr( void )
{
int i, error = 0, flag;
suffixLen = 0;
transTop = 0;
for ( i = 0; i < infixLen; i++ )
{
if ( infixExpr[i].n >= INT ) //当读到数字直接送至输出队列中
{
suffixExpr[suffixLen++] = infixExpr[i];
}
else if ( infixExpr[i].n > RBRACKET ) //当读入运算符时
{
//将栈中所有优先级高于或等于T的运算符弹出，送至输出队列
while ( transTop > 0 )
{
if ( pri( transStack[transTop-1], infixExpr[i].n ) )
{
suffixExpr[suffixLen++].n = transStack[--transTop];
}
else break;
}
//再把运算符入栈
transStack[transTop++] = infixExpr[i].n;
}
else if ( infixExpr[i].n == LBRACKET ) //读到左括号时总是将它压入栈中
{
transStack[transTop++] = infixExpr[i].n;
}
else //读到右括号时
{
flag = -1;
//将靠近栈顶的第一个左括号上面的运算符依次全部弹出，送至输出队列
while ( transTop > 0 )
{
if ( transStack[transTop-1] == LBRACKET )
{
flag = 0;
break;
}
suffixExpr[suffixLen++].n = transStack[--transTop];
}
//再丢弃左括号
if ( flag ) error = -1;
else transTop--;
}
}
while ( transTop > 0 )
{
if ( transStack[transTop-1] == LBRACKET )
{
error = -1;
}
suffixExpr[suffixLen++].n = transStack[--transTop];
}

//在测试阶段输出后缀表达式
#ifdef TEST
for ( i = 0; i < suffixLen; i++ )
{
switch ( suffixExpr[i].n )
{
case ADD: printf( "+ " );break;
case SUB: printf( "- " ); break;
case MUL: printf( "* " ); break;
case DIV: printf( "/ " ); break;
case INT: flag = suffixExpr[i].p; printf( "%d ", flag ); break;
case DOUBLE: printf( "%lf ", suffixExpr[i].p ); break;
}
}
#endif

return error;
}

//求最大值
__inline int maxn( int a, int b )
{
if ( a >= b ) return a;
return b;
}

//计算a和b做c运算的结果
struct ExprNode calcu( struct ExprNode *a, struct ExprNode *b, int c )
{
struct ExprNode r;
int i, j;
r.n = maxn( a->n, b->n );
switch ( c )
{
case ADD: r.p = (a->p)+(b->p); break;
case SUB: r.p = (a->p)-(b->p); break;
case MUL: r.p = (a->p)*(b->p); break;
case DIV: r.p = (a->p)/(b->p);
if ( r.n == INT )
{
i = a->p;
j = b->p;
if ( i%j ) r.n = DOUBLE;
}
break;
}
return r;
}

//计算后缀表达式
//表达式计算失败返回-1,否则为0
int calcu_expr( void )
{
int i, j, error = 0;
struct ExprNode a[2], r;
calcuTop = 0;
for ( i = 0; i < suffixLen && !error; i++ )
{
if ( suffixExpr[i].n >= INT ) //读到数字就将它压入栈S中
{
calcuStack[calcuTop++] = suffixExpr[i];
}
else //读到运算符
{
//从栈中依次弹出两个数X和Y
for ( j = 0; j < 2; j++ )
{
if ( calcuTop ) a[j] = calcuStack[--calcuTop];
else error = -1;
}
//以"X运算符Y"的形式计算出结果，再将结果压入栈S
if ( !error )
{
calcuStack[calcuTop++] = calcu( &a[1], &a[0], suffixExpr[i].n );
}
}
}
if ( calcuTop != 1 ) error = -1;
return error;
}

//输出运算结果
void show( void )
{
int i, n;
#ifndef TEST
for ( i = 0; i < suffixLen; i++ )
{
switch ( infixExpr[i].n )
{
case LBRACKET: printf( "( " ); break;
case RBRACKET: printf( ") " ); break;
case ADD: printf( "+ " );break;
case SUB: printf( "- " ); break;
case MUL: printf( "* " ); break;
case DIV: printf( "/ " ); break;
case INT: n = infixExpr[i].p; printf( "%d ", n ); break;
case DOUBLE: printf( "%lf ", infixExpr[i].p ); break;
}
}
#endif
if ( calcuStack[0].n == INT )
{
n = calcuStack[0].p;
printf( "= %d\n", n );
}
else
{
printf( "= %lf\n", calcuStack[0].p );
}
}

int main( int argc, char argv[] )
{
do
{
if ( input_expr() )
{
printf( "请输入正确的表达式!\n" );
continue;
}
if ( trans_expr() != -1 && calcu_expr() != -1 )
{
show();
}
else
{
printf( "请输入正确的表达式!\n" );
}
}while ( 1 );
return 0;
}