堆疊的綜合應用:數的轉換,括號匹配的檢驗,行編輯,迷宮求解,運算式求值
效果:
原始碼:
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/279857.html
標籤：其他
下一篇：力扣 -- 設計回圈佇列（題解）