算法与数据结构课程设计表达式求解问题(2)

输入：字符型，为了简便算法，只进行 + - * / 等简单运算，对算符的识别用简单的switch case；

所以 运算符栈的数据类型可以为 char

输入：数值，eg：1+1 中的 １如何处理？

为了方便，只能和输入统一为字符型，那么问题变为了，数值只能为１位整数（０～

９），因为程序目的是算法，所以可以简化为此。

但新问题来了，表达的运算中间结果或最终结果，不一定是 １位整数，eg：１+２*

５=？其中中间结果为１０，最终结果为１１。那么数据栈可以有以下２种结构设计：

方案１、数据栈元素类型为char，只保存 ０～９字符即ASCII码为 ３０H～３９

H，对于输入不转化，直接入数据栈，但在数据出栈参与运算前，先将字符０～９转为数字０～９。且最终结果也要逆向再转换一次，且若（中间）结果位数>１位，那么新的问题又引发了，如何存储和识别数据的位数。。。由此可见数据栈类型为char 会加大操作算法的难度。故放弃！

方案２、数据栈元素为int 型，当然，操作算法也要加强，但相比方案１的难度，

会小得多！加强如下：

输入数据（只能为１位数据，或加入位数识别函数），要先将字符０～９转化为 相

应数字０～９即ASCII减３０H（４８），这没什么难度。然后是（中间）结果，这里也没难度，只要结果在 -65536～+65535之间即可直接存入。因此选方案二。

6

二 详细设计

1程序模块

************************************************* ConsoleMain.c

*************************************************#define DEBUG 0 #include #include #include #include\

void main() {

char input=1;

int nShowInfo=1; // 是否显示帮助信息 do {

Evaluateexpression_r_r_r(nShowInfo); nShowInfo=0;

printf(\

getchar(); // 接收多的一个回车键字符 input=getchar(); if(input=='Y'|| input=='y')

7

input=1; else input=0; }while(input); }

************************************************************ EvaluateExp.h

************************************************************

#ifndef HEAD_LIST_SQ // 头文件定义宏，避免重复定义 #define HEAD_LIST_SQ

#define STACK_INIT_SIZE 100 #define STACK_INCREMENT_SIZE 10

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1 // 不可行的 #define OVERFLOW -2

typedef int Status;// 函数状态返回码为int 型

typedef char OptrElemType; // 运算符栈元素类型，可以用所有基本类型以及结构体类型等，

8

这里设为char 。

typedef int OpndElemType; // 数据栈元素类型 typedef struct {

OptrElemType * base; OptrElemType * top; int stacksize; }SqStackOptr; typedef struct {

OpndElemType * base; OpndElemType * top; int stacksize; }SqStackOpnd;

Status InitStackOptr(SqStackOptr *p_optr); Status InitStackOpnd(SqStackOpnd *p_opnd);

Status PushOptr(SqStackOptr *p_optr,OptrElemType OptrE); Status PushOpnd(SqStackOpnd *p_opnd,OpndElemType OpndE); Status PopOptr(SqStackOptr *p_optr,OptrElemType *p_optrE); Status PopOpnd(SqStackOpnd *p_opnd,OpndElemType *p_opndE); OptrElemType GetStackOptrTop(SqStackOptr *p_optr); OpndElemType GetStackOpndTop(SqStackOpnd *p_opnd); Status IsOptr(char ch); Status IsOpnd(char ch);

Status TranslateNum(OpndElemType *p_data,OptrElemType *p_ch); char CompareOptr(OptrElemType optr_A,OptrElemType optr_B);

Status OpndCount(OpndElemType *p_opnd_X,OpndElemType *p_opnd_A,OptrElemType

9

theta,OpndElemType *p_opnd_B); Status DestroyStackOptr(SqStackOptr *p); Status DestroyStackOpnd(SqStackOpnd *p); Status Evaluateexpression_r_r_r(int nShowInfo); #endif

三 程序运行

10