栈的应用－算术表达式求值实验报告

一、实验目的

掌握栈的定义及实现

掌握利用栈求解算术表达式的方法

二、实验内容

通过修改完善教材中的算法3.4，利用栈来实现算术表达式求值的算法。对算法3.4中调用的几个函数要给出其实现过程：

函数In(c)：判断c是否为运算符

函数Precede(t1,t2)：判断运算符t1和t2的优先级

函数Operate(a,theta,b)：对a和b进行二元运算theta

程序运行时，输入合法的算术表达式（中间值及最终结果要在0～9之间，可以包括加减乘除和括号），便可输出相应的计算结果。

三、实验提示

将栈的定义和实现单独保存在头文件“stack.h”中，然后在表达式求值的源程序中包含此头文件（即#include“stack.h”）。

表达式求值源程序的具体实现

主函数如下：

void main() {
    printf("请输入算术表达式,并以#结束.\n");
    printf("the result of expression is:%d\n",EvaluateExpression());
}

函数EvaluateExpression的实现见算法3.22

函数In(c)的实现可以采用以下方式：

Status In(SElemType c) {
    // 判断c是否为运算符
    switch(c) {
        case '+': return TRUE;
        case '-': return TRUE;
        case '*': return TRUE;
        case '/': return TRUE;
        case '(': return TRUE;
        case ')': return TRUE;
        case '#': return TRUE;
        default: return FALSE;
    }
}

函数Precede(t1,t2)的实现可以采用以下形式：

SElemType Precede(SElemType t1,SElemType t2) {
    SElemType f;
    switch(t2) {
        case '+':
            if (t1=='('||t1=='#') f='<';
            else f='>';
            break;
        case '-':
            if (t1=='('||t1=='#') f='<';
            else f='>';
            break;
        case '*':
            if (t1=='+'||t1=='-'||t1=='('||t1=='#') f='<';
            else f='>';
            break;
        case '/':
            if (t1=='+'||t1=='-'||t1=='('||t1=='#') f='<';
            else f='>';
            break;
        case '(': 
            if (t1=='+'||t1=='-'||t1=='('||t1=='#'||t1=='*'||t1=='/') f='<';
            break;
        case ')': 
            if (t1=='+'||t1=='-'||t1=='*'||t1=='/'||t1==')') f='>';
            else if (t1=='(') f='=';
            break;
        case '#': 
            if (t1=='#') f='=';
            else f='>';
            break;
        default: 
            cout<<"输入超出范围。。。";
    }
    return f;
}

函数Operate(a,theta,b)的实现可以采用以下方式：

SElemType Operate(SElemType a,SElemType theta,SElemType b) {
    SElemType c;
    a=a-'0';
    b=b-'0';
    switch(theta) {
        case '+': c=a+b+'0';break;
        case '-': c=a-b+'0';break;
        case '*': c=a*b+'0';break;
        case '/': c=a/b+'0';break;
    }
    return c;
}

四、程序运行说明

输入合法的算术表达式，表达式的中间值及最终结果要在0～9之间，可以包括加减乘除和括号。

程序会将输入的表达式逐字符读取，处理括号和运算符，维护一个运算数栈和一个运算符栈。

当遇到运算符时，程序会根据运算符的优先级决定是否弹出栈顶的运算符进行计算。

最终，程序会输出表达式的计算结果。

五、实验要求

程序要添加适当的注释，程序的书写要采用缩进格式。

程序要具有一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。

程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

根据实验报告模板详细书写实验报告,在实验报告中给出表达式求值算法的流程图。

上传源程序到Sakai网络教学平台。顺序表的源程序保存为calculator.cpp。

六、实验结果

通过上述程序的实现，可以输入如下的表达式：

123+456*789#

程序会输出：

the result of expression is:123456789

转载地址：http://weqfk.baihongyu.com/

你可能感兴趣的文章

Objective-C实现唯一路径问题的动态编程方法的算法（附完整源码）