实验四 栈的应用---算术表达式的计算

实验报告年级班号学号实验名称：栈的实现及其应用：算术表达式的计算实验日期2016年12月2日计算机科学与技术系2016年制一、实验环境32位操作系统下的Window平台Microsoft Visual C++二、实验目的掌握栈的实现及使用三、实验容1.实现栈的存储结构2.实现栈的基本操作的有关算法3.利用栈解决*算术表达式求值问题四、数据结构与算法思想描述顺序读取中缀表达式：1、当遇到数字时，将数字入数字栈2、当遇到操作符时，与操作符栈栈顶比较：If(当前操作符优先级大于操作符栈栈顶的优先级)If(非”)”操作符)将当前操作符进操作符栈;ElseWhile(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;ElseIf(非(“操作符)While(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;Continue;(直到当前操作符比栈顶操作符优先级大)Else将当前操作符进操作符栈;3、While(操作符栈非空)操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;4、在数字栈取最后结果并输出。

五、程序清单//10*8^2+16.3+5*(5.2*5+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666 //100+(-100)-(-10^2) = 100//(((2016-2017+(((2015-2014)))))) = 0//-1+(((((((((1^0))))))))+100%10^2 = 0#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<iomanip>#include<map>using namespace std;const int MAX = 105;typedef double Type;typedef struct{Type TypeStack[MAX];char charStack[MAX];int TypeTop, charTop;}Stack;//初始化栈void InitStack(Stack *S){S->charTop = S->TypeTop = 0; }//判断charStack是否为空bool IsEmpty_Char(Stack S){return S.charTop == 0;}//判断TypeStack是否为空bool IsEmpty_Type(Stack S){return S.TypeTop == 0;}//判断charStack是否为满bool IsFull_Char(Stack S){return S.charTop == MAX;}//判断TypeStack是否为满bool IsFull_Type(Stack S){return S.TypeTop == MAX;}void Push_Char(Stack *S, char ch){//charStack不为满则入栈，否则输出提示if(!IsFull_Char(*S))S->charStack[S->charTop++] = ch;elsecout << " The CharStack Is Full! " << endl; }void Push_Type(Stack *S, Type a){//TypeStack不为满则入栈，否则输出提示if(!IsFull_Type(*S))S->TypeStack[S->TypeTop++] = a;elsecout << " The TypeStack Is Full! " << endl; }char Pop_Char(Stack *S){if(!IsEmpty_Char(*S)){S->charTop--;return S->charStack[S->charTop];}elsecout << " The CharStack Is Empty! " << endl;return -1;}Type Pop_Type(Stack *S){if(!IsEmpty_Type(*S)){S->TypeTop--;return S->TypeStack[S->TypeTop];}elsecout << " The TypeStack Is Empty! " << endl;return -1;}char Top_Char(Stack S){if(!IsEmpty_Char(S))return S.charStack[--S.charTop];elsecout << " The CharStack Is Empty! " << endl;return -1;}Type Top_Type(Stack S){if(!IsEmpty_Type(S))return S.TypeStack[--S.TypeTop];elsecout << " The TypeStack Is Empty! " << endl;return -1;}Type Calculate(Type left, Type right, char op){Type value = 0;switch(op){case '+': value = left + right; break;case '-': value = left - right; break;case '*': value = left * right; break;case '/': if(right != 0)value = left / right;elsecout << "被除数不能为零!" << endl;break;case '%': i f(right != 0)value = (int)left % (int)right;elsecout << "被余数不能为零!" << endl;break;case '^': value = pow(left,right);/*value = 1;if(right >= 0)while(right--)value *= left;else{right = -right;while(right--)value /= left;}*/}return value;}void Computer(char *mid_equotion, Type len){Type right, left , result;char *p_mid_equotion = mid_equotion;char after_equotion = ' ';map<char,Type> Oper;Oper['#'] = 1; Oper['('] = 2; O per['+'] = 3;Oper['-'] = 3; O per['*'] = 4; Oper['/'] = 4;Oper['%'] = 4; Oper['^'] = 5; Oper[')'] = 6;Stack MyStack;InitStack(&MyStack);Push_Char(&MyStack,'#');char top_oper, current_oper;for(;*p_mid_equotion != '\0';){top_oper = Top_Char(MyStack);current_oper = *p_mid_equotion;if(!Oper[current_oper]){Push_Type(&MyStack,strtod(p_mid_equotion, &p_mid_equotion));continue;}//end ifelse //为操作符{if(Oper[current_oper] > Oper[top_oper]){if(current_oper != ')')Push_Char(&MyStack,current_oper);else{while(top_oper != '('){right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, Top_Char(MyStack)));Pop_Char(&MyStack);top_oper = Top_Char(MyStack);}Pop_Char(&MyStack);}//end else}//end ifelse{if(current_oper == '('){Push_Char(&MyStack,current_oper);if(*(p_mid_equotion + 1) == '-')Push_Type(&MyStack,0);}else{right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper));Pop_Char(&MyStack);continue;}}//end else}//end elsep_mid_equotion++;}//end fortop_oper = Pop_Char(&MyStack);while(top_oper != '#'){right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper));top_oper = Pop_Char(&MyStack);}// cout << setprecision(6) << "\nThe Result = " << (result = Pop_Type(&MyStack)) << endl;printf("The Result = %lf\n\n",(result = Pop_Type(&MyStack)));}int main(){char s[MAX] = "";Type i = 0;cout << "请输入你要求值的表达式!(以-1结束)\n";while(cin >> s && strcmp(s,"-1") != 0){Computer(s,strlen(s));cout << "请输入你要求值的表达式!(以-1结束)\n";}return 0;}六、程序执行结果及其分析对“+” , “-” , “*” , “/” , “%” , “^”运算的实现可运算多位数和小数，求余，求平方，括号里包含负数如（-1），及首个数字为负数如-1+1。

利用栈来实现算术表达式求值的算法利用栈来实现算术表达式求值的算法算术表达式是指按照一定规则组成的运算式，包含数字、运算符和括号。

在计算机中，求解算术表达式是一项基本的数学运算任务。

根据算术表达式的性质，我们可以考虑利用栈这一数据结构来实现求值算法。

一、算法思路首先，我们需要明确一个重要概念——逆波兰表达式（ReversePolish notation）。

逆波兰表达式是一种没有括号的算术表达式，其运算规则是先计算后面的数字和运算符，再计算前面的数字和运算符。

例如，对于算术表达式“3+4*5-6”，其对应的逆波兰表达式为“3 45 * +6 -”。

那么，我们可以利用栈来实现将中缀表达式转化为逆波兰表达式的过程，具体步骤如下：1. 创建两个栈——操作数栈和操作符栈。

2. 从左到右扫描中缀表达式的每一个数字和运算符，遇到数字则压入操作数栈中，遇到运算符则进行如下操作：（1）如果操作符栈为空或当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符压入操作符栈中。

（2）如果当前运算符的优先级小于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入操作数栈中，重复此过程直到遇到优先级较低的运算符或操作符栈为空为止，然后将当前运算符压入操作符栈中。

3. 扫描完中缀表达式后，若操作符栈不为空，则将其中所有运算符弹出并加入操作数栈中。

4. 最终，操作数栈中存放的就是逆波兰表达式，我们可以按照逆波兰表达式的计算规则来计算其结果。

二、算法优点利用栈来实现算术表达式求值的算法具有以下优点：1. 代码简洁易懂，易于实现和维护。

2. 由于将中缀表达式转化为逆波兰表达式后，可以减少运算符的优先级关系而消除括号，从而减少求值的复杂度，提高程序的执行效率。

三、代码实现下面是利用栈来实现算术表达式求值的算法的Python代码实现：```pythonclass Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[-1]def is_empty(self):return len(self.items) == 0def size(self):return len(self.items)def calculate(op_num1, op_num2, operator):if operator == "+":return op_num1 + op_num2elif operator == "-":return op_num1 - op_num2elif operator == "*":return op_num1 * op_num2elif operator == "/":return op_num1 / op_num2def infix_to_postfix(infix_expr):opstack = Stack()postfix_expr = []prec = {"+": 1, "-": 1, "*": 2, "/": 2, "(": 0} token_list = infix_expr.split()for token in token_list:if token.isdigit():postfix_expr.append(token)elif token == '(':opstack.push(token)elif token == ')':top_token = opstack.pop()while top_token != '(':postfix_expr.append(top_token)top_token = opstack.pop()else:while (not opstack.is_empty()) and(prec[opstack.peek()] >= prec[token]):postfix_expr.append(opstack.pop())opstack.push(token)while not opstack.is_empty():postfix_expr.append(opstack.pop())return " ".join(postfix_expr)def postfix_eval(postfix_expr):opstack = Stack()token_list = postfix_expr.split()for token in token_list:if token.isdigit():opstack.push(int(token))else:op_num2 = opstack.pop()op_num1 = opstack.pop()result = calculate(op_num1, op_num2, token) opstack.push(result)return opstack.pop()infix_expr = "3 + 4 * 5 - 6"postfix_expr = infix_to_postfix(infix_expr)print(postfix_expr)print(postfix_eval(postfix_expr))```四、总结算术表达式求值是一项常见的数学运算任务，利用栈这一数据结构来实现求值算法是一种简单有效的方法，它将中缀表达式转化为逆波兰表达式后，可以消除括号并减少运算符的优先级关系，从而提高程序的执行效率。

一、实验目的1. 理解栈的基本概念、特点及逻辑结构；2. 掌握栈的顺序存储和链式存储结构；3. 熟练掌握栈的基本操作，如入栈、出栈、判断栈空等；4. 理解栈在递归算法中的应用；5. 探究栈在实际问题中的应用。

二、实验内容1. 栈的定义与特点2. 栈的顺序存储结构3. 栈的链式存储结构4. 栈的基本操作5. 栈在递归算法中的应用6. 栈在实际问题中的应用三、实验步骤1. 栈的定义与特点（1）栈是一种后进先出（LIFO）的数据结构；（2）栈的元素只能从一端（栈顶）进行插入和删除操作；（3）栈具有两个基本操作：入栈和出栈。

2. 栈的顺序存储结构（1）使用数组来实现栈的顺序存储结构；（2）定义一个数组作为栈的存储空间；（3）定义栈顶指针top，初始值为-1；（4）定义栈的最大容量maxSize。

3. 栈的链式存储结构（1）使用链表来实现栈的链式存储结构；（2）定义一个链表节点，包含数据域和指针域；（3）定义栈顶指针top，初始时指向链表头节点。

4. 栈的基本操作（1）入栈操作：将元素插入到栈顶，栈顶指针向上移动；（2）出栈操作：删除栈顶元素，栈顶指针向下移动；（3）判断栈空：判断栈顶指针是否为-1，是则栈空，否则栈非空。

5. 栈在递归算法中的应用（1）斐波那契数列的递归算法；（2）汉诺塔问题；（3）迷宫问题。

6. 栈在实际问题中的应用（1）括号匹配问题；（2）表达式求值问题；（3）递归函数的调用栈。

四、实验结果与分析1. 栈的定义与特点通过本次实验，我们深入理解了栈的基本概念、特点及逻辑结构，掌握了栈的后进先出特性。

2. 栈的顺序存储结构使用数组实现栈的顺序存储结构，操作简单高效。

在实验过程中，我们实现了栈的基本操作，如入栈、出栈、判断栈空等。

3. 栈的链式存储结构使用链表实现栈的链式存储结构，具有灵活性和扩展性。

在实验过程中，我们实现了栈的基本操作，如入栈、出栈、判断栈空等。

4. 栈的基本操作通过实验，我们熟练掌握了栈的基本操作，如入栈、出栈、判断栈空等，为后续递归算法和实际问题中的应用奠定了基础。

栈的应用实验报告导言：在计算机科学领域中，数据结构是一项非常重要的基础。

栈是一种常用的数据结构，它在算法设计和软件开发中具有广泛的应用。

本实验旨在探索栈的应用，并通过实际操作来加深对栈数据结构的理解。

实验目的：1. 了解栈的定义和基本操作。

2. 掌握栈在实际问题中的应用方法。

3. 培养问题分析和解决的能力。

实验步骤：1. 实现栈的基本操作：压入(push)和弹出(pop)。

2. 针对以下实际问题，设计并实现相应的栈应用。

一、括号匹配问题括号匹配问题是指在一个字符串中，括号的开闭配对是否正确。

例如，"{[()]}"是正确的括号匹配，而"{[(])}"则是错误的括号配对。

通过使用栈，我们可以很方便地解决这个问题。

算法步骤如下：1. 遍历字符串的每个字符。

2. 若字符是左括号，则将其压入栈中。

3. 若字符是右括号，则检查栈是否为空，若为空则配对错误；若非空，则弹出栈顶元素并检查是否与右括号匹配。

4. 遍历结束后，若栈为空，则括号匹配正确，否则匹配错误。

二、函数调用问题在计算机程序中，函数的调用和返回遵循"先进后出"的原则，即后调用的函数先返回。

栈提供了一种便捷的方式来管理函数调用和返回过程。

在实际的编程中，我们可以使用栈来存储函数的局部变量和返回地址等信息。

例如，以下是一个简单的函数调用示例：1. 函数A调用函数B。

2. 函数B在栈中保存局部变量和返回地址。

3. 函数B执行完毕后，从栈中弹出局部变量和返回地址，程序继续执行函数A。

三、逆波兰表达式求值问题逆波兰表达式是一种不使用括号来表示表达式的方法，而是通过运算符放置在操作数之后的方式来表示。

例如，表达式"2 3 +"等价于中缀表达式"2 + 3"。

利用栈，我们可以很方便地对逆波兰表达式进行求值。

算法步骤如下：1. 遍历逆波兰表达式的每个元素。

2. 若元素是操作数，则将其压入栈中。

实验报告年级班号学号实验名称：栈的实现及其应用：算术表达式的计算实验日期2016年12月2日计算机科学与技术系2016年制一、实验环境32位操作系统下的Window平台Microsoft Visual C++二、实验目的掌握栈的实现及使用三、实验容1.实现栈的存储结构2.实现栈的基本操作的有关算法3.利用栈解决*算术表达式求值问题四、数据结构与算法思想描述顺序读取中缀表达式：1、当遇到数字时，将数字入数字栈2、当遇到操作符时，与操作符栈栈顶比较：If(当前操作符优先级大于操作符栈栈顶的优先级)If(非”)”操作符)将当前操作符进操作符栈;ElseWhile(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;ElseIf(非(“操作符)While(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;Continue;(直到当前操作符比栈顶操作符优先级大)Else将当前操作符进操作符栈;3、While(操作符栈非空)操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;4、在数字栈取最后结果并输出。

五、程序清单//10*8^2+16.3+5*(5.2*5+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666 //100+(-100)-(-10^2) = 100//(((2016-2017+(((2015-2014)))))) = 0//-1+(((((((((1^0))))))))+100%10^2 = 0#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<iomanip>#include<map>using namespace std;const int MAX = 105;typedef double Type;typedef struct{Type TypeStack[MAX];char charStack[MAX];int TypeTop, charTop;}Stack;//初始化栈void InitStack(Stack *S){S->charTop = S->TypeTop = 0; }//判断charStack是否为空bool IsEmpty_Char(Stack S){return S.charTop == 0;}//判断TypeStack是否为空bool IsEmpty_Type(Stack S){return S.TypeTop == 0;}//判断charStack是否为满bool IsFull_Char(Stack S){return S.charTop == MAX;}//判断TypeStack是否为满bool IsFull_Type(Stack S){return S.TypeTop == MAX;}void Push_Char(Stack *S, char ch){//charStack不为满则入栈，否则输出提示if(!IsFull_Char(*S))S->charStack[S->charTop++] = ch;elsecout << " The CharStack Is Full! " << endl; }void Push_Type(Stack *S, Type a){//TypeStack不为满则入栈，否则输出提示if(!IsFull_Type(*S))S->TypeStack[S->TypeTop++] = a;elsecout << " The TypeStack Is Full! " << endl; }char Pop_Char(Stack *S){if(!IsEmpty_Char(*S)){S->charTop--;return S->charStack[S->charTop];}elsecout << " The CharStack Is Empty! " << endl;return -1;}Type Pop_Type(Stack *S){if(!IsEmpty_Type(*S)){S->TypeTop--;return S->TypeStack[S->TypeTop];}elsecout << " The TypeStack Is Empty! " << endl;return -1;}char Top_Char(Stack S){if(!IsEmpty_Char(S))return S.charStack[--S.charTop];elsecout << " The CharStack Is Empty! " << endl;return -1;}Type Top_Type(Stack S){if(!IsEmpty_Type(S))return S.TypeStack[--S.TypeTop];elsecout << " The TypeStack Is Empty! " << endl;return -1;}Type Calculate(Type left, Type right, char op){Type value = 0;switch(op){case '+': value = left + right; break;case '-': value = left - right; break;case '*': value = left * right; break;case '/': if(right != 0)value = left / right;elsecout << "被除数不能为零!" << endl;break;case '%': i f(right != 0)value = (int)left % (int)right;elsecout << "被余数不能为零!" << endl;break;case '^': value = pow(left,right);/*value = 1;if(right >= 0)while(right--)value *= left;else{right = -right;while(right--)value /= left;}*/}return value;}void Computer(char *mid_equotion, Type len){Type right, left , result;char *p_mid_equotion = mid_equotion;char after_equotion = ' ';map<char,Type> Oper;Oper['#'] = 1; Oper['('] = 2; O per['+'] = 3;Oper['-'] = 3; O per['*'] = 4; Oper['/'] = 4;Oper['%'] = 4; Oper['^'] = 5; Oper[')'] = 6;Stack MyStack;InitStack(&MyStack);Push_Char(&MyStack,'#');char top_oper, current_oper;for(;*p_mid_equotion != '\0';){top_oper = Top_Char(MyStack);current_oper = *p_mid_equotion;if(!Oper[current_oper]){Push_Type(&MyStack,strtod(p_mid_equotion, &p_mid_equotion));continue;}//end ifelse //为操作符{if(Oper[current_oper] > Oper[top_oper]){if(current_oper != ')')Push_Char(&MyStack,current_oper);else{while(top_oper != '('){right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, Top_Char(MyStack)));Pop_Char(&MyStack);top_oper = Top_Char(MyStack);}Pop_Char(&MyStack);}//end else}//end ifelse{if(current_oper == '('){Push_Char(&MyStack,current_oper);if(*(p_mid_equotion + 1) == '-')Push_Type(&MyStack,0);}else{right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper));Pop_Char(&MyStack);continue;}}//end else}//end elsep_mid_equotion++;}//end fortop_oper = Pop_Char(&MyStack);while(top_oper != '#'){right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper));top_oper = Pop_Char(&MyStack);}// cout << setprecision(6) << "\nThe Result = " << (result = Pop_Type(&MyStack)) << endl;printf("The Result = %lf\n\n",(result = Pop_Type(&MyStack)));}int main(){char s[MAX] = "";Type i = 0;cout << "请输入你要求值的表达式!(以-1结束)\n";while(cin >> s && strcmp(s,"-1") != 0){Computer(s,strlen(s));cout << "请输入你要求值的表达式!(以-1结束)\n";}return 0;}六、程序执行结果及其分析对“+” , “-” , “*” , “/” , “%” , “^”运算的实现可运算多位数和小数，求余，求平方，括号里包含负数如（-1），及首个数字为负数如-1+1。

栈的应⽤——表达式求值 表达式求值是程序设计语⾔编译中的⼀个基本问题，它的实现就是对“栈”的典型应⽤。

本⽂针对表达式求值使⽤的是最简单直观的算法“算符优先法”。

本⽂给出两种⽅式来实现表达式求值，⽅式⼀直接利⽤中缀表达式求值，需要⽤到两个栈，操作数栈和操作符栈。

⾸先置操作数栈为空栈，操作符栈仅有“#”⼀个元素。

依次读⼊表达式中的每个字符，若是操作数则进操作数栈，若是操作符则和操作符栈的栈顶运算符⽐较优先权作相应操作，直⾄整个表达式求值完毕。

⽅式⼆⾸先把中缀表达式转换为后缀表达式并存储起来，然后利⽤读出的后缀表达式完成求值，其本质上是⽅式⼀的分解过程。

表达式求值的代码如下：#include <iostream>#include "stack"#include "map"using namespace std;/* 只能求⼀位整数的加减乘除混合运算 */map<char, pair<int, int>> priority; // 存放各个操作符的栈内栈外优先级,first是栈内,second是栈外char infix[50]; // 存放初始的中缀表达式char postfix[50]; // 存放转化的后缀表达式int result;void MakePriority() // 构造运算符优先级表{priority.insert(make_pair('#', make_pair(0, 0))); // isp(#)=0, icp(#)=0priority.insert(make_pair('\n', make_pair(0, 0))); // isp(\n)=0, icp(\n)=0 表达式结尾的'#'⽤'\n'代替,这样可以省略表达式末尾的结束符'#'priority.insert(make_pair('(', make_pair(1, 6))); // isp(()=1, icp(()=6priority.insert(make_pair('*', make_pair(5, 4))); // isp(*)=5, icp(*)=4priority.insert(make_pair('/', make_pair(5, 4))); // isp(/)=5, icp(/)=4priority.insert(make_pair('%', make_pair(5, 4))); // isp(%)=5, icp(%)=4priority.insert(make_pair('+', make_pair(3, 2))); // isp(+)=3, icp(+)=2priority.insert(make_pair('-', make_pair(3, 2))); // isp(-)=3, icp(-)=2priority.insert(make_pair(')', make_pair(6, 1))); // isp())=6, icp())=1}void InfixToPostfix() // 把中缀表达式转换为后缀表达式{int i = 0;stack<char> optrStack; // 操作符栈char optr; // optr为栈顶的操作符optrStack.push('#');while (!optrStack.empty()){if (isdigit(infix[i])) // 是操作数则直接输出(追加到postfix结尾){postfix[strlen(postfix)] = infix[i];postfix[strlen(postfix) + 1] = '\0';i++; // 读⼊中缀表达式的下⼀个字符}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出栈顶操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈{optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first)// icp(infix[i]) < isp(optr),optr退栈并输出{postfix[strlen(postfix)] = optr;postfix[strlen(postfix) + 1] = '\0';optrStack.pop();}else// icp(infix[i]) = isp(optr),退栈但不输出,若退出的是'(',则继续读⼊下⼀个字符{optrStack.pop();if (optr == '(')i++;}}}}void CalculateByPostfix() // 通过后缀表达式求值{int i = 0;stack<int> opndStack; // 操作数栈int left, right; // 左右操作数int value; // 中间结果int newOpnd;while (postfix[i] != '#' && i < strlen(postfix)){switch (postfix[i]){case'+':right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left - right;opndStack.push(value);break;case'*':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left * right;opndStack.push(value);break;case'/':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:newOpnd = (int)(postfix[i] - 48); // 操作数直接⼊栈opndStack.push(newOpnd);break;}i++;}result = opndStack.top();}void CalculateByInfix() // 直接利⽤中缀表达式求值{int i = 0;stack<char> optrStack; // 操作符栈stack<int> opndStack; // 操作数栈char optr; // optr为操作符栈顶的操作符int left, right, value; // 左右操作数以及中间结果optrStack.push('#');optr = optrStack.top();while (!optrStack.empty()) // 直到操作符栈为空{if (isdigit(infix[i])) // 是操作数, 进操作数栈{value = (int)(infix[i] - 48);opndStack.push(value);i++;}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出操作符栈顶的操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈 {optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first) // icp(infix[i]) < isp(optr),optr退栈并输出{optrStack.pop();right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();switch (optr){case'+':value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':value = left - right;opndStack.push(value); // 中间结果⼊栈break;case'*':value = left * right;opndStack.push(value); // 中间结果⼊栈break;case'/':if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:break;}}else{optrStack.pop();if (optr == '(')i++;}}}result = opndStack.top();}int main(){MakePriority(); // 构造运算符优先级表cout << "请输⼊中缀表达式：";cin >> infix;cout << "直接利⽤中缀表达式求值为：";CalculateByInfix();cout << result << endl;cout << "转化为后缀表达式：";InfixToPostfix();for (int i = 0;i < strlen(postfix);i++){cout << postfix[i];}cout << endl;cout << "利⽤后缀表达式求值为：";CalculateByPostfix();cout << result << endl;return0;} 为了⽅便起见，本⽂只是简单的设计了⼀个针对⼀位整数的四则运算进⾏求值的算法，对于处理多位整数的四则运算，需要对本⽂接受输⼊的数据类型进⾏“升阶”，把字符数组换成字符串数组，将⼀个整数的多位数字存⼊⼀个字符串进⾏处理。

浙江大学城市学院实验报告课程名称_________ 数据结构与算法实验工程名称实验四栈的应用---算术表达式的计算学生姓名专业班级学号实验成绩指导老师<签名)日期一.实验目的和要求1•进一步掌握栈的基本操作的实现。

2•掌握栈在算术表达式的计算方面的应用。

二.实验内容1.编写程序对后缀表达式进行求值<利用栈)，即输入任一个后缀表达式，输出该后缀表达式的值。

要求：把栈的基本操作的实现函数存放在文件stack.h 中，在主程序文件test4.cpp中包含后缀表达式求值函数doubleCompute(char *str>与主函数。

主函数可以参考如下：void mai n(>{char str[50]。

printf("请输入一个后缀表达式：">。

gets(str>。

printf("后缀表达式值为：%f\n", Compute(str> > 。

}2 .填写实验报告，实验报告文件取名为report4.doc。

3. 上传实验报告文件report4.doc与源程序文件stack.h及test4.cpp到Ftp服务器上你自己的文件夹下。

三.函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路void Change( char *S1, char *S2 >中缀表达式转化为后缀表达式double Compute(char *str>::后缀表达式求值void InitStack (Stack &S> 初始化栈Int EmptyStack (Stack S>判断栈是否为空void Push(Stack &S, ElemType item:入栈ElemType Pop(Stack &S> 出栈ElemType Peek(Stack S> 取栈顶元素void ClearStack (Stack &S> 清除栈四.实验结果与分析包括运行结果截图等五■心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。

数据结构实验二——算术表达式求值实验报告算术表达式求值实验报告一、引言算术表达式求值是计算机科学中一个重要的基础问题，它涉及到了数据结构和算法的应用。

本实验旨在通过实现一个算术表达式求值的程序，加深对数据结构中栈的理解和应用，并掌握算术表达式的求值过程。

二、实验目的1. 理解算术表达式的基本概念和求值过程；2. 掌握栈的基本操作和应用；3. 实现一个能够正确求解算术表达式的程序；4. 进一步熟悉编程语言的使用。

三、实验内容1. 设计并实现一个栈的数据结构；2. 实现算术表达式求值的算法；3. 编写测试用例，验证程序的正确性；4. 进行性能测试，分析算法的时间复杂度。

四、实验方法与步骤1. 设计栈的数据结构在本实验中，我们选择使用数组来实现栈的数据结构。

栈的基本操作包括入栈（push）、出栈（pop）、判断栈空（isEmpty）和获取栈顶元素（top）等。

2. 算术表达式求值算法算术表达式求值的一种常用算法是通过后缀表达式进行求值。

具体步骤如下： - 将中缀表达式转换为后缀表达式；- 通过栈来求解后缀表达式；- 返回最终的计算结果。

3. 编写测试用例编写一系列测试用例，包括不同类型的算术表达式，以验证程序的正确性。

例如：- 简单的四则运算表达式：2 + 3 * 4 - 5；- 包含括号的表达式：(2 + 3) * (4 - 5)；- 包含多位数的表达式：12 + 34 * 56；- 包含浮点数的表达式：3.14 + 2.71828。

4. 性能测试和时间复杂度分析针对不同规模的输入数据，进行性能测试，记录程序的运行时间。

同时，分析算法的时间复杂度，验证算法的效率。

五、实验结果与分析我们设计并实现了一个栈的数据结构，并成功地完成了算术表达式求值的程序。

通过对一系列测试用例的验证，我们发现程序能够正确地求解各种类型的算术表达式，并返回正确的计算结果。

在性能测试中，我们对不同规模的输入数据进行了测试，并记录了程序的运行时间。

栈的应用实验报告栈的应用实验报告引言：栈是一种常见的数据结构，它具有后进先出（Last In First Out，LIFO）的特点。

在计算机科学中，栈被广泛应用于各种领域，如编译器、操作系统、图形处理等。

本实验旨在通过实际应用场景，探索栈的应用。

一、栈的基本概念和操作栈是一种线性数据结构，它由一系列元素组成，每个元素都有一个前驱元素和一个后继元素。

栈的基本操作包括入栈（Push）和出栈（Pop）。

入栈将元素添加到栈的顶部，而出栈则将栈顶元素移除。

此外，栈还具有查看栈顶元素（Top）和判断栈是否为空（IsEmpty）的操作。

二、栈在表达式求值中的应用栈在表达式求值中发挥着重要作用。

例如，当我们需要计算一个数学表达式时，可以通过将表达式转换为后缀表达式，并利用栈来进行求值。

栈中存储操作数，当遇到运算符时，从栈中弹出相应数量的操作数进行计算，再将结果入栈。

通过这种方式，我们可以实现高效的表达式求值。

三、栈在函数调用中的应用栈在函数调用中也扮演着重要角色。

当我们调用一个函数时，计算机会将函数的返回地址、参数和局部变量等信息存储在栈中。

这样，当函数执行完毕后，可以从栈中恢复之前的上下文，继续执行调用函数的代码。

栈的这种特性使得递归函数的实现成为可能，同时也为程序的模块化提供了便利。

四、栈在迷宫求解中的应用栈在迷宫求解中也能发挥重要作用。

当我们需要找到从起点到终点的路径时，可以利用栈来存储当前路径上的位置。

从起点开始，我们按照某种策略选择下一个位置，并将其入栈。

如果当前位置无法继续前进，则将其出栈，并选择下一个位置。

通过不断重复这个过程，直到找到终点或者栈为空，我们就能得到迷宫的解。

五、栈在撤销和恢复操作中的应用栈在撤销和恢复操作中也能发挥重要作用。

当我们在编辑文档或者绘图时，经常需要进行撤销和恢复操作。

栈可以用来记录每次操作的状态，当用户选择撤销时，从栈中弹出最近的操作，并将文档或图形恢复到之前的状态。

通过这种方式，我们可以提供良好的用户体验，同时也方便用户进行操作的回溯。

陕西科技大学实验报告姓名班级学号实验组别实验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等）一、实验名称：栈的实现与应用二、实验目的：1.掌握栈的定义。

2.掌握栈基本操作的实现，并能用于解决实际问题。

三、实验环境：Windows2000,Visual C++ 6.0四、实验内容：1.实现栈的如下基本操作：push,pop,isempty,isfull,createstack。

2.利用栈的基本操作实现conversion()函数，该函数能将任意输入的十进制整数转换为二进制形式表示。

五、实验原理：1．栈的基本概栈（stack）是一种特殊的线性表。

是将线性表的插入和删除均是仅在表的一端进行，通常将允许插入和删除的一端称栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。

同时，表的一端称栈底(Bottom)。

当栈中没有元素时称为空栈。

栈的插入操作被形象的称为进栈或入栈，删除操作称为出栈或退栈。

2.栈的结构特性通常栈可以用线性的方式存储，分配一块连续的存储区域存放栈中的元素，并用一个变量指向当前的栈顶。

每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。

元素是以a1，a2，a3,...，an的顺序进栈的，而退栈的次序却是an，...，a3，a2，a1。

栈的修改是按后进先出的顺序进行的。

因此，栈又称为后进先出的线性表，简称为LIFO表.3.栈的建立C语言中用一维数组来实现栈.假设栈的元素个数最大不超过Maxsize，所有的元素都具有同一个数据类datatype，则可以用下列方式来定义栈的类型stack：typedef struct{datatype elements[maxsize];int Top;}Stack;4.栈的压入（push）void push(ST,x)stak *ST ;ElemType x;{if(ST->top==Maxsize-1)printf(“栈上溢出！\n”);else{ST->top++;ST->s[ST->top]=x;}}5.栈的弹出pop（ST）void pop(ST,x)stak *ST ;{if(ST->top==-1)printf(“栈上溢出！\n”);elseST->top--;}6.判断栈是否为空（isempty）int sempty(ST)stack *ST;{if(ST->top==-1)return(1);elsereturn(0)}7.读栈顶元素top（ST，x）Void pop（ST，x）Stack *STElemType *x；{If（ST->top==-1）printf(“无栈顶元素!\n”);else *x=ST->s[ST->top];}8.取栈顶元素ptop（ST）ElemType ptop(ST)Stack *ST;{Elemtype x; /*将栈顶元素赋给x*/top (ST,&x); /* 将栈顶元素弹出*/pop(ST); /*返回x值*/return(x);}五.实验流程：六.程序代码#include<stdio.h>#include<stdlib.h>#define maxsize 1024typedef int datatype;typedef struct{datatype elements[maxsize];int Top;}Stack;void setNull(Stack *S){S->Top=-1;}int isfull(Stack *S){if(S->Top>=maxsize-1)return(1);else return(0);}int isempty(Stack *S){if(S->Top>=0)return(0);else return(1);}void push(Stack *S,datatype E){if(S->Top>=maxsize-1){printf("Stack Overflow");}else{S->Top++;S->elements[S->Top]=E;}}datatype *pop(Stack *S){datatype *temp;if(isempty(S)){printf("Stack Underfiow");return(NULL);}else{S->Top--;temp=(datatype *)malloc(sizeof(datatype));*temp=S->elements[S->Top+1];return(temp);}}void conversion(int n){int r,m;Stack S;setNull(&S);r=n;while(r){m=r%2;if(isfull(&S))printf("Over flow\n");else push(&S,m);r=r/2;}printf("转换后的二进制为\n");while(!isempty(&S))printf("%d",*(pop(&S)));printf("\n");}void main(){int num;printf("请输入需要转换为二进制的十进制数据\n");scanf("%d",&num);conversion(num);}七.实验截图八.实验小结此次上机实验，我不仅对栈的存储等操作有了一定的认识，也对十进制到二进制的转换有了深刻的理解，同时对编译程序的算法思想有了新的认识，还让我深刻的体会到了链表的重要性以及其应用的方便，并且对指针加深了印象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。