stackexam.cpp

数据结构C语言中的顺序栈的实现

#include <cstdlib>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include "../header/SqStack.h"

using namespace std;

void conversion(int Num, int d);        //数制转换,Num待转换的数，d转换的进制
bool brackMatch(char* str);             //括号匹配，str待检验的字符串
SqStack m_pStack;

void ShowMenu()
{
	system("cls");
	printf("\n================The Menu for Stack==================\n");
	printf("    1. Decial To binary,octal,Hex \n");
	printf("    2. match of brackets\n");
	printf("    3. Line Editor\n");
	printf("    4. Maze Path Finder\n");
	printf("    5. Evaluate Expression\n");
	printf("    q: Quit\n");
	printf("================The Menu end================\n");
	printf("Please Make your Choice(1~5,q-quit):\t");
}

int main(int argc, char* argv[])
{
	char choice;
	while(1)
	{
		ShowMenu();

  		choice = getche();
		switch(choice)
		{
			case '1':           //Conversion
				{
					int Num = 0, d;
					printf("\nplease input the Num:\t");
					scanf("%d", &Num);
					printf("\nYou want to transform it to(1~9):\t");
					scanf("%d", &d);
					printf("\nOK, you want to change %d to %d\n", Num, d);
					conversion(Num, d);
					getche();
				}
				break;
			case '2':           //bracket matching
				{
					char strMatch[255];
					printf("\n 请输入一个字符串，可以包括{[()]}以及其它符号:\t");
					scanf("%s", strMatch);
					
					if(brackMatch(strMatch))
					    printf("你输入的串%s中的括号是匹配的!\n");
					else
					    printf("你输入的串%s中的括号是不匹配的!\n");
					    
		  	    	getch();
				}
				break;
			case '3':

				getch();
				break;
			case '4':
				{

					getch();
				}
				break;
			case '5':

					getch();
				break;
			case 'q':
				getch();
				exit(0);
				break;
			default:
				break;
	    }
	}

	DestroyStack(m_pStack);
	return 0;
}

void conversion(int Num, int d)
{
	if(d <= 0 || d >= 10) return;     //十进制不用转换
	
	InitStack(m_pStack);
	while(Num)
	{
		Push(m_pStack, Num%d);
		Num = Num/d;
	}
	
	printf("The result is :\t");
	SElemType e;
	while(!IsStackEmpty(m_pStack))
	{
		Pop(m_pStack, e);
		printf("%d", e);
	}
	printf("\n");
	
	DestroyStack(m_pStack);
}

bool isAmongStr(const char* str, char elem)
{
	int i=0;
	for(i=0;i<strlen(str);i++)
	{
		if(str[i] == elem)
		    return true;
	}
	return false;
}

bool brackMatch(char* str)
{
	const char* leftB = "{[(";
	const char* rightB = ")]}";
	
	if(strcmp(str,"")==0)       //str==""
	    return false;

	int strLen = strlen(str);
	bool matched = true;
	int i=0;
	while(i < strLen && matched)
	{
		char ch = str[i];
		if(isAmongStr(leftB, ch))       //左括号
            Push(m_pStack, ch);
		else if(isAmongStr(rightB,ch))  //右括号
		{
			SElemType expElem;
			switch(ch)
			{
				case '}':
				    expElem = '{';
				    break;
				case ']':
					expElem = '[';
					break;
				case ')':
					expElem = '(';
				default:
					break;
			}
			
			SElemType topElem = ' ';
			if(Pop(m_pStack, topElem) != OK)    //Empty Stack
			    matched = false;
			    
			if(topElem != expElem)
			    matched = false;
		}
		i++;
	}

	if(!IsStackEmpty(m_pStack))
	    matched = false;
	
	return matched;
}