1 #define _CRT_SECURE_NO_WARNINGS 1 2 3 #include4 #include 5 #include<string.h> 6 #include 7 #include 8 using namespace std; 9 10 #define StackSize 10 11 typedef char DataType; 12 13 /*-------------------栈的基本操作------------------*/ 14 typedef struct SqStack 15 { 16 DataType data[StackSize]; //保存栈中元素,元素的类型为DataType 17 int top; //栈指针,top的取值范围0~StackSize-1;top=-1表示栈空;top=StackSize-1表示栈满;top++表示进栈;top--表示出栈 18 19 }SqStack; 20 21 //初始化 22 void InitStack(SqStack& pst)//pst为引用型参数(C++) 23 { 24 pst.top = -1; 25 } 26 27 //进栈:栈指针加1,将栈顶元素放进栈顶处 28 void Push(SqStack& pst, DataType x) 29 { 30 if (StackSize - 1 == pst.top) 31 { 32 printf("栈已满\n"); 33 return; 34 } 35 else { 36 pst.top++; 37 pst.data[pst.top] = x; 38 } 39 40 } 41 42 //出栈:先将栈顶元素取出,然后将栈指针减一 43 DataType Pop(SqStack& pst) 44 { 45 if (-1 == pst.top) 46 { 47 printf("栈为空\n"); 48 return -1; 49 } 50 else { 51 int x = pst.data[pst.top]; 52 pst.top--; 53 return x; 54 } 55 } 56 57 //查看栈顶元素:将栈指针top出的元素返回 58 DataType GetTop(SqStack st) 59 { 60 if (-1 == st.top) 61 { 62 printf("栈为空\n"); 63 return -1; 64 } 65 else 66 return st.data[st.top]; 67 } 68 69 //判断栈是否为空 70 bool StackEmpty(SqStack st) 71 { 72 if (-1 == st.top) 73 { 74 return 1; 75 } 76 else { 77 return 0; 78 } 79 } 80 81 void ClearStack(SqStack& pst) { 82 for (int i = pst.top; i > 0; i--) { 83 Pop(pst); 84 } 85 cout << "栈已清空" << endl; 86 } 87 88 //打印 89 void SeqListPrint(const SqStack st) 90 { 91 int i = 0; 92 for (i = 0; i < StackSize; i++) 93 { 94 printf("%d ", st.data[i]); 95 } 96 printf("\n"); 97 } 98 99 /*---------------------栈的应用--------------------*/ 100 //进制转换 101 void conversion() { 102 SqStack s; 103 SqStack& ps = s; 104 InitStack(s); 105 int N; 106 cout << "输入你要转换的数字:" << endl; 107 cin >> N; 108 cout << "输入你要转换的进制:" << endl; 109 int n; 110 cin >> n; 111 while (N) { 112 Push(s, N % n); 113 N = N / n; 114 } 115 while (!StackEmpty(s)) { 116 DataType e; 117 e = Pop(s); 118 cout << e; 119 } 120 } 121 122 //括号匹配,需要将DateType改为char 123 void Kuohao() { 124 //输入为左边括号时直接入栈,输入为右边括号时出栈一个,输入的符号和出栈的符号做匹配判断 125 SqStack s; 126 SqStack& ps = s; 127 InitStack(s); 128 129 char a[6]; 130 cout << "输入6个括号" << endl; 131 for (int i = 0; i < 6; i++) { 132 cin >> a[i]; 133 } 134 for (int i = 0; i < 6; i++) { 135 if (StackEmpty(s)) { 136 if (a[i] == '{' || a[i] == '(' || a[i] == '[') { 137 Push(s, a[i]); 138 } 139 else { 140 cout << "无法匹配"; 141 break; 142 } 143 } 144 else { 145 if (a[i] == '{' || a[i] == '(' || a[i] == '[') { 146 Push(s, a[i]); 147 } 148 else { 149 DataType e = Pop(s); 150 if (e == '{' && a[i] != '}') { 151 cout << "匹配失败!" << endl; 152 break; 153 } 154 else if(e == '[' && a[i] != ']'){ 155 cout << "匹配失败!" << endl; 156 break; 157 } 158 else if (e == '(' && a[i] != ')') { 159 cout << "匹配失败!" << endl; 160 break; 161 } 162 cout << "匹配成功" << endl; 163 } 164 } 165 } 166 } 167 168 //行编辑程序。输入#退格,输入@退行 169 void LineEdit() { 170 SqStack s; 171 SqStack& ps = s; 172 InitStack(s); 173 DataType ch = getchar(); 174 while (ch != '\n') { //终端接受第一个字符 175 switch (ch) 176 { 177 case '#': 178 Pop(s); break; 179 case '@': 180 ClearStack(s); break; 181 default: 182 Push(s, ch); break; 183 }//switch 184 ch = getchar(); 185 }//whilenn 186 SeqListPrint(s); 187 } 188 189 void Test() 190 { 191 SqStack s; 192 SqStack& ps = s; 193 InitStack(s); 194 195 Push(ps, 1); 196 Push(ps, 2); 197 Push(ps, 3); 198 Push(ps, 4); 199 Push(ps, 5); 200 SeqListPrint(s); 201 202 printf("此时栈顶元素为:%2d\n", GetTop(s)); 203 204 printf("出栈元素为:%2d", Pop(ps)); 205 printf(",此时栈顶元素为:%2d\n", GetTop(s)); 206 printf("出栈元素为:%2d", Pop(ps)); 207 printf(",此时栈顶元素为:%2d\n", GetTop(s)); 208 209 StackEmpty(s); 210 } 211 212 int main() 213 { 214 //Test(); 215 //conversion(); 216 //Kuohao(); 217 LineEdit(); 218 system("pause"); 219 return 0; 220 }
Original: https://www.cnblogs.com/JIAcheerful/p/16150304.html
Author: 云霄雨霁
Title: 数据结构3.2栈的应用
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/622517/
转载文章受原作者版权保护。转载请注明原作者出处!