数据结构 实验四 c++实现 20-11-25
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构 实验四 c++实现 20-11-25，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4718字，纯文字阅读大概需要7分钟。
内容图文
目录
一、任务
- 利用顺序表建立一个栈。分别编写入栈函数和出栈函数，对键盘输入的，数量未知的整数进行出栈和入栈的操作。每次调用入栈函数或出栈函数时，实现一个整数的入栈或出栈；出栈的整数需要打印出来。
- 利用链表建立一个栈。分别编写入栈函数和出栈函数，对键盘输入的，数量未知的整数进行出栈和入栈的操作。每次调用入栈函数或出栈函数时，实现一个整数的入栈或出栈；出栈的整数需要打印出来。
- 利用顺序栈或链式栈求解表达式（a+b）*(c-d)的值(可手工把中缀表达式转换为后缀表达式)。其中的操作数a，b，c，d为0到9之间的整数。
二、中缀表达式转化为后缀表达式
- 1.遇到数字直接输出；
- 2.遇到符号：
- a.栈空直接入栈；
- b.右括号：弹出并输出直到栈顶为左括号，弹出左括号；
- c.其他符号：
- A.若优先级大于栈顶，当前字符入栈；
- B.若当前字符优先级小于等于栈顶，出栈并输出直到栈顶优先级小于当前字符；
三、由后缀表达式计算
- 1.遇到数字入栈；
- 2.遇到符号，先出在右，后出在左，做运算，运算结果入栈；
- 3.遍历完后，栈顶即为结果。
四、代码实现
/*LinkedStack.h*/
#include <iostream>
#define NodePosition Node<T> *
using namespace std;
template <typename T>
struct Node
{
T data;
NodePosition next;
Node(T d=0):data(d),next(NULL){}
};
template <typename T>
class LinkedStack
{
private :
NodePosition top;
public:
LinkedStack():top(NULL){}
~LinkedStack(){}
void push(T d){
NodePosition p = new Node<T>(d);
if(top == NULL)
{
top = p;
return;
}
p->next = top;
top=p;
}
T pop()
{
if (top = NULL)
{
cout<<"empty!"<<endl;
return 0;
}
NodePosition p = top;
T d = top->data;
top = top->next;
delete p;
return d;
}
T Top()
{
return top->data;
}
bool IsEmpty()
{
if(top) return true;
else return false;
}
};
/*SeqStack.h*/
#include <iostream>
#define MAXSIZE 100
using namespace std;
template <typename T>
class SeqStack
{
private:
T data[MAXSIZE];
int top;
public:
SeqStack():top(-1){}
~SeqStack(){}
void Push(T d)
{
if (top == MAXSIZE - 1)
{
cout<<"STACK IS FULL"<<endl;
return;
}
data[++top]=d;
}
T pop()
{
if(top == -1)
{
cout<<"STACK IS EMPTY"<<endl;
return 0;
}
return data[top--];}
T Top(){return data[top];}
bool IsEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}
};
#include <iostream>
#include <string>
#include "SeqStack.h"
#include "LinkedStack.h"
using namespace std;
int PrioJud ( char a ) // 优先级判断
{
if ( a == '*' || a == '/' )
{
return 2;
}
else if ( a == '+' || a == '-' )
{
return 1;
}
else if ( a == '(' )
{
return 0;
}
}
string InfixToRPN ( string str1 ) //中缀表达式转化为后缀表达式
{
string str2;
SeqStack<char> S;
for ( int i = 0; i < str1.size() ; i++ )
{
if ( str1[i] >= '0' && str1[i] <= '9' )
{
str2 += str1[i];
}
else if ( S.IsEmpty() )
{
S.Push ( str1[i] );
}
else if ( str1[i] == ')' )
{
while ( S.Top() != '(' )
{
str2 += S.pop();
}
S.pop();
}
else if ( str1[i] == '(' )
{
S.Push ( str1[i] );
}
else if ( PrioJud ( str1[i] ) <= PrioJud ( S.Top() ) )
{
while ( PrioJud ( str1[i] ) <= PrioJud ( S.Top() ) )
{
str2 += S.pop();
if ( S.IsEmpty() )
break;
}
S.Push ( str1[i] );
}
else if ( PrioJud ( str1[i] ) > PrioJud ( S.Top() ) )
{
S.Push ( str1[i] );
};
}
while ( !S.IsEmpty() )
{
str2 += S.pop();
}
return str2;
}
int Cout ( char c, char a, char b )
{
int A, B;
if ( c == '+' )
{
return ( int ) ( a - '0' ) + ( int ) ( b - '0' );
}
else if ( c == '-' )
{
return ( int ) ( a - '0' ) - ( int ) ( b - '0' );
}
else if ( c == '*' )
{
return ( int ) ( a - '0' ) * ( int ) ( b - '0' );
}
else if ( c == '/' )
{
return ( int ) ( a - '0' ) / ( int ) ( b - '0' );
}
}
int CoutByRPN ( string str ) //由后缀表达式计算
{
char a, b;
SeqStack<char> S;
for ( int i = 0; i < str.size(); i++ )
{
if ( str[i] >= '0' && str[i] <= '9' )
S.Push ( str[i] );
else
{
b = S.pop();
a = S.pop();
S.Push ( Cout ( str[i], a, b ) + '0' );
}
}
return S.Top() - '0';
}
int main()
{
int flag = 1;
string str;
LinkedStack<int> S2;
SeqStack<int> S1;
int m;
cout << "****************SeqStack*********************" << endl;
while ( flag )
{
cout << "1.push" << endl;
cout << "2.pop" << endl;
cout << "3.top" << endl;
cout << "4.IsEmpty?" << endl;
cout << "0.exit" << endl;
cin >> m;
switch ( m )
{
case 1:
int q;
cin >> q;
S1.Push ( q );
break;
case 2:
cout << S1.pop() << endl;;
break;
case 3:
cout << S1.Top() << endl;;
break;
case 4:
if ( S1.IsEmpty() )
cout << "It is empty." << endl;
else
cout << "It is not empty." << endl;
break;
case 0:
flag = 0;
break;
}
}
cout << "*********************LinkedStack******************" << endl;
flag = 1;
while ( flag )
{
cout << "1.push" << endl;
cout << "2.pop" << endl;
cout << "3.top" << endl;
cout << "4.IsEmpty?" << endl;
cout << "0.exit" << endl;
cin >> m;
switch ( m )
{
case 1:
int q;
cin >> q;
S2.push ( q );
break;
case 2:
cout << S2.pop() << endl;;
break;
case 3:
cout << S2.Top() << endl;
break;
case 4:
if ( S2.IsEmpty() )
cout << "It is empty." << endl;
else
cout << "It is not empty." << endl;
break;
case 0:
flag = 0;
break;
}
}
cout << "*****************Caculate*************" << endl;
cin >> str;
cout << InfixToRPN ( str ) << endl;
cout << CoutByRPN ( InfixToRPN ( str ) );
return 0;
}
内容总结
以上是互联网集市为您收集整理的数据结构 实验四 c++实现 20-11-25全部内容，希望文章能够帮你解决数据结构 实验四 c++实现 20-11-25所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】