效果:
源码:
Stack.h:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct _Position {//迷宫坐标
int _x;
int _y;
}Position;
#define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定
typedef Position ElemType;
typedef struct _SqStack {
ElemType* base;//栈底指针
ElemType* top;//栈顶指针
}SqStack;
//构造一个空栈S
bool InitStack(SqStack& S) {
S.base = new ElemType[MaxSize];//为顺序表分配一个最大容量为Maxsize的空间
if (!S.base) return false;//空间分配失败
S.top = S.base;//top初始化为base,空栈
return true;
}
//插入元素e为新的栈顶元素
bool PushStack(SqStack& S, ElemType e) {
if (S.top - S.base == MaxSize) return false;//栈满
*(S.top++) = e;
return true;
}
//删除S的栈顶元素,暂存在变量e中
bool PopStack(SqStack& S, ElemType& e) {
if (S.base == S.top) return false;
e = *(--S.top);
return true;
}
//返回S的栈顶元素,栈顶指针不变
ElemType* GetTop(SqStack& S) {
if (S.top != S.base) {//栈非空
return S.top - 1;//返回栈顶的值,栈顶元素不变
}
else {
return NULL;
}
}
//返回栈中元素的个数
int GetSize(SqStack& S) {
return (S.top - S.base);
}
//判断栈是否为空
bool IsEmpty(SqStack& S) {
if (S.top == S.base) {
return true;
}
else {
return false;
}
}
//摧毁栈
void DestoryStack(SqStack& S) {
if (S.base) {
free(S.base);
S.base = NULL;
S.top = NULL;
}
}
main.cpp
#include<iostream> //输入的表达式要以'#'结尾，如‘5+6*3/(3-1)#’
#include<stack>
#include"Stack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXSIZE 100
using namespace std;
stack<char> opter; //运算符栈
stack<double> opval; //操作数栈
stack<char> Line;//行编辑
stack<int>chang;// 转换
#define ROW 6
#define COL 6
typedef struct _Maze {
int map[ROW][COL];
}Maze;
//二进制转换
void change1() {
int N;
int e;
cout << "请输入要转换的数字:";
cin >> N;
while (N) {
chang.push(N % 2);
N = N / 2;
}
while (!chang.empty()) {
e = chang.top();
chang.pop();
cout << e;
}
cout << endl;
}
//八进制转换
void change2() {
int N;
int e;
cout << "请输入要转换的数字:";
cin >> N;
while (N) {
chang.push(N % 8);
N = N / 8;
}
while (!chang.empty()) {
e = chang.top();
chang.pop();
cout << e;
}
cout << endl;
}
//十六进制转换
void change3() {
int N;
int e;
int q;//暂时保存取余16的余数
cout << "请输入要转换的数字:";
cin >> N;
while (N) {
q = N % 16;
if (q <= 9) {
chang.push(q);
}
else {
switch (q)
{
case 10:
chang.push('A');
break;
case 11:
chang.push('B');
break;
case 12:
chang.push('C');
break;
case 13:
chang.push('D');
break;
case 14:
chang.push('E');
break;
case 15:
chang.push('A');
break;
case 16:
chang.push('F');
break;
default:
break;
}
}
N = N / 16;
}
while (!chang.empty()) {
e = chang.top();
if (e <= 9) {
chang.pop();
cout << e;
}
else
{
chang.pop();
cout << char(e);
}
}
cout << endl;
}
void show() {
while (true)
{
int choose;
cout << "1.-------二进制转换---------" << endl;
cout << "2.-------八进制转换---------" << endl;
cout << "3.-------十六进制转换-------" << endl;
cout << "4----------退出--------------" << endl;
cout << "请你选择要输入的功能:";
cin >> choose;
switch (choose) {
case 1:
change1();
break;
case 2:
change2();
break;
case 3:
change3();
break;
case 4:
return;
break;
default:
break;
}
}
}
//判断左右两个括号是否是同类型的括号
int Match(char ch, char c) {
if (ch == '(' && c == ')') return 1;
if (ch == '[' && c == ']') return 1;
if (ch == '{' && c == '}') return 1;
return 0;
}
//检测括号是否匹配
void CheckMatch(char* p) {
char c;
while (*p) {
switch (*p) {
/*如果是左括号，将其入栈*/
case '(':
case '[':
case '{':
Line.push(*p++);
break;
case ')':
case ']':
case '}':
/*栈为空 ，说明没有左括号入栈*/
if (Line.empty()) {
printf("缺少左括号！\n");
return;
}
else {
/*取出栈顶元素，将栈顶元素与读入的右括号比较，如果栈顶括号与
右括号匹配，则将栈顶括号出栈*/
c = Line.top();
if (Match(c, *p)) {
Line.pop();
}
/*栈顶括号与读入的括号不匹配*/
else {
printf("左右括号不匹配！\n");
return;
}
}
/*如果读入的不是括号，指针后移一位*/
default:
p++;
}
}
/*栈为空，所有的字符序列读入完毕，说明括号序列匹配*/
if (Line.empty()) {
printf("括号匹配！\n");
}
else {
printf("缺少右括号！\n");
}
}
void show2() {
while (true)
{
int choose;
cout << "1.--------开始--------" << endl;
cout << "2.---------退出--------" << endl;
cout << "请输入你要选择的功能:" << endl;
cin >> choose;
switch (choose){
case 1:
char* p;
char ch[MAXSIZE];
p = ch;
//memset(ch, 0x00, sizeof(ch));
printf("请输如一个带括号的表达式：\n");
gets_s(ch);
gets_s(ch);
CheckMatch(p);
break;
case 2:
return;
break;
default:
break;
}
}
}
//清除一行
void Clearstack() {
while (!Line.empty()) {
Line.pop();
}
}
void LinkEdit()
{
char ch;
// int e;
ch = getchar();
ch = getchar();
while (ch != EOF && ch != '\n')
{
switch (ch)
{
case '@':
Clearstack();
break;
case '#':
Line.pop();
break;
default:
Line.push(ch);
}
ch = getchar();
}
}
void show3() {
while (true)
{
cout << "1.-------开始-------" << endl;
cout << "2.-------退出-------" << endl;
int choose;
cin >> choose;
switch (choose){
case 1:
cout << "请输入一串数字:" << endl;
LinkEdit();
while (Line.size())
{
cout << Line.top() << endl;
Line.pop();
}
break;
case 2:
return;
break;
default:
break;
}
}
}
//迷宫的初始化
void InitMaze(Maze* m, int map[ROW][COL]) {
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
m->map[i][j] = map[i][j];
}
}
}
//打印迷宫
void PrintMaze(Maze* m) {
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
printf("%d", m->map[i][j]);
}
printf("\n");
}
printf("\n");
}
//判断是否为有效入口
int IsValidEnter(Maze* m, Position cur) {
assert(m);
if ((cur._x == 0 || cur._x == ROW - 1) || (cur._y == 0 || cur._y == COL - 1) && (m->map[cur._x][cur._y] == 1)) {
return 1;
}
else {
return 0;
}
}
//判断当前节点的下一个结点能否走通
int IsNextPass(Maze* m, Position cur, Position next) {
assert(m);
//判断next结点是否为cur 的下一节点
if (((next._x == cur._x) && ((next._y == cur._y + 1) || (next._y == cur._y - 1))) //在同一行上并且相邻
|| ((next._y == cur._y) && ((next._x == cur._x + 1) || (next._x == cur._x - 1)))) {//或在同一列上并且相邻
//判断下一个节点是否在迷宫里面
if (((next._x >= 0 && next._x < ROW) || (next._y >= 0 && next._y < COL)) && (m->map[next._x][next._y] == 1)) {
return 1;
}
}
return 0;
}
//判断当前节点是不是有效的迷宫出口
int IsValidExit(Maze* m, Position cur, Position enter) {
assert(m);
//这里首先得保证该节点不是入口点，其次只要它处在迷宫的边界即可
if ((cur._x != enter._x || cur._y != enter._y) && ((cur._x == 0 || cur._x == ROW - 1) || (cur._y == 0 || cur._y == COL - 1)))
{
return 1;
}
else {
return 0;
}
}
//找出迷宫通路
int PassMaze(Maze* m, Position enter, SqStack* s) {
assert(m && IsValidEnter(m, enter) == 1); //对给的迷宫的入口进行合法性判断
Position cur = enter;
Position next;
PushStack(*s, cur); //首先将迷宫的入口压入栈中
m->map[cur._x][cur._y] = 2; //将入口值改为 2
//PrintMaze(m);
while (!IsEmpty(*s)) {
cur = *GetTop(*s);
//printf("cur: %d %d\n",cur._x, cur._y);
if (IsValidExit(m, cur, enter) == 1) //判断当前位置是否出口
return 1;
//尝试向左一步：看当前节点的左一个节点能不能走通
next = cur;
next._y = cur._y - 1;
if (IsNextPass(m, cur, next) == 1) {
PushStack(*s, next);
m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
//PrintMaze(m);
continue;
}
//尝试向上一步:看当前节点的上一个节点能不能走通
next = cur;
next._x = cur._x - 1;
if (IsNextPass(m, cur, next) == 1) //next 节点能够走通时，将其压入 栈中
{
PushStack(*s, next);
m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
//将 next 节点的值等于 cur 节点的值加 1
//PrintMaze(m);
continue;
}
//右：看当前节点的向右的一个节点能不能走通
next = cur;
next._y = cur._y + 1;
if (IsNextPass(m, cur, next) == 1) {
PushStack(*s, next);
m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
//PrintMaze(m);
continue;
}
//下：看当前节点的下一个节点能不能走通
next = cur;
next._x = cur._x + 1;
if (IsNextPass(m, cur, next) == 1) {
PushStack(*s, next);
m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
//PrintMaze(m);
continue;
}
//走到这里说明当前节点的四个方向都走不通，进行回溯，看前一个节点 未被遍历的方向是否还能走通
Position tmp;
PopStack(*s, tmp);
}
return 0;
}
void show4() {
int map[ROW][COL] = { //用二维数组描绘迷宫：1 代表通路，0 代表墙
0,0,1,0,0,0,
0,0,1,1,1,0,
0,0,1,0,0,0,
0,1,1,1,1,0,
0,0,1,0,1,0,
0,0,0,0,1,0
};
Maze m;
Position enter; //迷宫入口
enter._x = 0;
enter._y = 2;
InitMaze(&m, map);
PrintMaze(&m);
//system("pause");
//exit(0);
SqStack s; //定义栈，保存已走过的坐标轨迹，便于回溯
InitStack(s); //栈的初始
int ret = PassMaze(&m, enter, &s); //使用栈和回溯法解开迷宫
if (ret) {
printf("恭喜你！终于找到了出口~\n");
}
else {
printf("不是我笨！实在没有出口~\n");
}
PrintMaze(&m);
}
int getIndex(char theta) //获取theta所对应的索引
{
int index = 0;
switch (theta)
{
case '+':
index = 0;
break;
case '-':
index = 1;
break;
case '*':
index = 2;
break;
case '/':
index = 3;
break;
case '(':
index = 4;
break;
case ')':
index = 5;
break;
case '#':
index = 6;
default:break;
}
return index;
}
char getPriority(char theta1, char theta2) //获取theta1与theta2之间的优先级
{
const char priority[][7] = //算符间的优先级关系
{
{ '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=','0' },
{ '>','>','>','>','0','>','>' },
{ '<','<','<','<','<','0','=' },
};
int index1 = getIndex(theta1);
int index2 = getIndex(theta2);
return priority[index1][index2];
}
double calculate(double b, char theta, double a) //计算b theta a
{
switch (theta)
{
case '+':
return b + a;
case '-':
return b - a;
case '*':
return b * a;
case '/':
return b / a;
default:
break;
}
}
double getAnswer() //表达式求值
{
opter.push('#'); //首先将'#'入栈opter
int counter = 0; //添加变量counter表示有多少个数字相继入栈，实现多位数的四则运算
char c = getchar();
while (c != '#' || opter.top() != '#') //终止条件
{
if (isdigit(c)) //如果c在'0'~'9'之间
{
if (counter == 1) //counter==1表示上一字符也是数字，所以要合并，比如12*12，要算12，而不是单独的1和2
{
double t = opval.top();
opval.pop();
opval.push(t * 10 + (c - '0'));
counter = 1;
}
else {
opval.push(c - '0'); //将c对应的数值入栈opval
counter++;
}
c = getchar();
}
else {
counter = 0; //counter置零
switch (getPriority(opter.top(), c)) //获取运算符栈opter栈顶元素与c之间的优先级，用'>'，'<'，'='表示
{
case '<': //<则将c入栈opter
opter.push(c);
c = getchar();
break;
case '=': //=将opter栈顶元素弹出，用于括号的处理
opter.pop();
c = getchar();
break;
case '>': //>则计算
char theta = opter.top();
opter.pop();
double a = opval.top();
opval.pop();
double b = opval.top();
opval.pop();
opval.push(calculate(b, theta, a));
break;
}
}
}
return opval.top(); //返回opval栈顶元素的值
}
void show5() {
int t; // 需要计算的表达式的个数
cin >> t;
getchar();
while (t--)
{
while (!opter.empty()) opter.pop();
while (!opval.empty()) opval.pop();
double ans = getAnswer();
cout << ans << endl << endl;
getchar();
}
}
int main()
{
while (true)
{
int choose;
cout << "-------欢迎来到栈的应用!!!!!!!--------" << endl;
cout << "1.------数字转换" << endl;
cout << "2.------括号匹配的检验" << endl;
cout << "3.------行编辑" << endl;
cout << "4-------迷宫求解" << endl;
cout << "5-------表达式求值" << endl;
cout << "6--------退出" << endl;
cout << "请你输入要选择的功能:";
cin >> choose;
switch (choose)
{
case 1:
show();
break;
case 2:
show2();
break;
case 3:
show3();
break;
case 4:
show4();
break;
case 5:
show5();
break;
case 6:
return 0;
break;
default:
break;
}
}
return 0;
}
复制概述 Mysql内建的复制功能是构建大型，高性能应用程序的基...
4月4清明假期修改了一天的project依旧实现不了RTL视图只能出来一个模块另外两个...
在这里，假设读者了解基本的 ajax 技术或更多。我仅仅阐述一个现象，一个解决方...
播放视频文件流程图 H264概述 ?????????对摄像头采集的每一帧视频需要进行编码由...
?? Bash shell 学习笔记1——字符串操作 ??1.字符串的长度 ??获取字符串长度的语...
现象： 安装VS2019时，下面的界面运行后退出，没有自动弹出下一步的安装界面 原...
需要最新版本的bingo.js支持 ， 下载bingo.js ， 下载本DEMO 方法： pageSwitch(...
文章目录 一、HTTP基础 1.1 HTTP 基本概念 1.1.1 状态码 1.1.2 http 常见字段 1....
今天在日常维护一个网站时，发现该网站的留言程序没有经过严格的验证过滤，导致...
Vim是一个类似于Vi的著名的功能强大、高度可定制的文本编辑器，在Vi的基础上改进...
