相关说明

  • 文章内容:数据结构实验

  • 所属课程:数据结构

  • 实验学时:2学时

  • 授课学院:武汉理工大学计算机学院

  • 作者主页:https://blog.csdn.net/cxh_1231


实验目的:

  掌握栈与队列的基本结构和操作方法,并能利用其解决实际问题。


实验内容: 

  输入一个表达式(4+2*4#),利用栈求表达式的值。(只对整数求值,目前只考虑操作数为个位数的情况,即24+34*34这种情况不考虑)


提示:

  1,先实现栈的基本操作:初始化,入栈,出栈等。

  2,首先将一个中缀式变成后缀式,然后,对后缀式求值。

  3,可用顺序栈或者链栈实现。


实验代码:

注:手机无法正常显示请在电脑端打开此文章

  1// 栈与队列的应用.cpp: 定义控制台应用程序的入口点。  
 2#include <iostream>  
 3using namespace std;  
 4#define STACK_INIT_SIZE 100  
 5#define STACKINCREASE 10  
 6#define SElemType int  
 7#define Status int  
 8#define OK 1  
 9#define OVERFLOW -1  
10#define ERROR 0  
11//运算符优先级表    
12char Prior[7][7] =  
13{       // '+' '-' '*' '/' '(' ')' '#'    
14    /*'+'*/'>','>','<','<','<','>','>',  //当栈中的符号是加号时,此加号与下一个运算符进行比较优先级  
15    /*'-'*/'>','>','<','<','<','>','>',  //下面几行类似  
16    /*'*'*/'>','>','>','>','<','>','>',  
17    /*'/'*/'>','>','>','>','<','>','>',  
18    /*'('*/'<','<','<','<','<','=',' ',  
19    /*')'*/'>','>','>','>',' ','>','>',  
20    /*'#'*/'<','<','<','<','<',' ','='  
21};  
22char Precede(int a, int b) {//判断优先级  
23    return Prior[a][b];  
24}  
25typedef struct {  
26    SElemType *base;  
27    SElemType *top;  
28    int stacksize;  
29}SqStack;  
30//构造空栈S  
31Status InitStack(SqStack &S) {  
32    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));  
33    if (!S.base) return OVERFLOW;  
34    S.top = S.base;  
35    S.stacksize = STACK_INIT_SIZE;  
36    return OK;  
37}  
38//入栈操作  
39Status Push(SqStack &S, SElemType e) {  
40    if (S.top - S.base >= S.stacksize) {    //栈满,追加空间  
41        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREASE) * sizeof(SElemType));  
42        if (!S.base) return ERROR;      //存储空间分配失败  
43        S.top = S.base + S.stacksize;  
44        S.stacksize += STACKINCREASE;  
45    }  
46    *S.top = e;  
47    S.top++;  
48    return OK;  
49}  
50//出栈操作  
51Status Pop(SqStack &S, SElemType &e) {  
52    if (S.top == S.base) return ERROR;  
53    e = *--S.top;  
54    return e;  
55}  
56//取栈顶元素  
57Status GetTop(SqStack S, SElemType &e) {  
58    if (S.top == S.base) {     //如果栈为空,返回错误  
59        return ERROR;  
60    }  
61    e = *(S.top - 1);  
62    return e;  
63}  
64int change(char a) {           //将字符转换成数字  
65    if (a == '+') return 0;    //主要是因为建立的栈为int型    
66    if (a == '-') return 1;    //方便与存储到栈中  
67    if (a == '*') return 2;  
68    if (a == '/') return 3;  
69    if (a == '(') return 4;  
70    if (a == ')') return 5;  
71    if (a == '#') return 6;  
72    else return a-48;  
73}  
74//判断是不是运算符  
75int In(char c) {  
76    if (c-48>=0 && c-48<= 9) return ERROR;  
77    else return OK;  
78}  
79//进行运算  
80int Operator(int a, int theta, int b) {      
81    if (theta == 0) return a + b;  
82    if (theta == 1) return a - b;  
83    if (theta == 2) return a*b;  
84    if (theta == 3) return a/b;  
85}  
86//输入表达式并求值  
87int EvaluateExperession() {  
88    SqStack optr; //运算符栈  
89    SqStack opnd; //运算数栈  
90    InitStack(optr);  //初始化  
91    InitStack(opnd);  //初始化  
92    Push(optr, 6);    //初始栈底元素为#,用数字6表示  
93    char c[50];       //用字符串数组来保存输入的表达式  
94    int i=0,  x,  result;  
95    cin >> c;         //输入表达式  
96    do  
97    {  
98        if (!In(c[i])) {     //如果不是运算符,将其进运算数栈  
99            Push(opnd, change(c[i]));  
100            i++;  
101        }  
102        else {               //是运算符,比较优先级并进行相关操作  
103            switch (Precede(GetTop(optr, x), change(c[i]))) {  
104            case '<':        //当前栈顶元素优先级低,新运算符入栈  
105                Push(optr, change(c[i]));  
106                i++;  
107                break;  
108            case '=':        //两个运算符相等,为左右括号,取出  
109                Pop(optr, x);  
110                i++;  
111                break;  
112            case '>':        //当前栈顶运算符优先级高,进行计算  
113                int a, b, theta;  
114                Pop(optr, theta);  //取当前栈顶运算符  
115                Pop(opnd, b);      //取栈顶运算数b,并从栈中删除  
116                Pop(opnd, a);      //取栈顶运算数a,并从栈中删除  
117                Push(opnd, Operator(a, theta, b));   //进行计算,将计算结果        
118                break;  
119            }  
120        }  
121    } while ( c[i] );  
122    return GetTop(opnd, result);  
123}  
124int main()  
125
{  
126    cout << "请输入一个表达式(以#结束):";  
127    cout << "计算得结果为:"<<EvaluateExperession() << endl;  
128    return 0;  
129}  


运行结果:


您的支持就是我们前进的动力

本篇文章来源于微信公众号: 计科