数据结构栈，括号匹配，表达式求值

栈

栈的定义：只允许在一端进行插入或删除操作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一段进行插入和删除操作。

栈顶（Top）：线性表允许进行插入和删除的一端。

栈底（Bottom）：固定的，不允许进行插入和删除的另一端。

空栈：不含任何元素。

如上图：a1为栈底元素，an为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1，a2，... ,an 而出栈次序为an，...，a2，a1。栈的明显的操作特征为后进先出（Last In First Out，LIFO）,故又称后进先出的线性表。

栈的基本操作

1）InitStack（&S）：初始化空栈S

2）StackEmpty（S）：判断一个栈是否为空

3）Push（&S，x）：进栈，若栈未满，则将x加入使之成为新栈顶

4）Pop（&S，&x）：出栈，若栈非空，则将栈顶元素，并用x返回

5）GetTop(S，&x)：读栈顶元素，若栈顶元素非空，则用x返回栈顶元素

6）DestroyStack(&S)：销毁栈，并释放栈S占用的存储空间

顺序栈的实现

采用顺序存储的栈称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。

栈的顺序存储类型可以用以下表示：

#define MAXSIZE 100         //栈中元素的最大个数
typedef struct {
    ElemType data[MAXSIZE]; //存放栈中元素
    int top;                //栈顶指针
} SqStack;

进栈

bool Push(SqStack& S, ElemType x){
    if( S.top == MAXSIZE - 1 ){ //栈满，报错
        return false;        
    }
    S.top ++ ;                  //栈顶指针加1
    S.data[S.top] = x;          //入栈
    return true;
}

出栈

bool Pop(SqStack& S, ElemType& x){
    if( S.top == -1 ){          //栈空，报错
        return false;
    }
    x = S.data[S.top];
    S.top --;
    return true;
}

老师的代码

#include 
#include 

#define STACK_MAX_SIZE 10


typedef struct CharStack {
    int top;

    int data[STACK_MAX_SIZE]; //The maximum length is fixed.
} *CharStackPtr;


void outputStack(CharStackPtr paraStack) {
    for (int i = 0; i <= paraStack->top; i ++) {
        printf("%c ", paraStack->data[i]);
    }// Of for i
    printf("rn");
}// Of outputStack


CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
	resultPtr->top = -1;

	return resultPtr;
}//Of charStackInit


void push(CharStackPtr paraStackPtr, int paraValue) {
    // Step 1. Space check.
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
        printf("Cannot push element: stack full.rn");
        return;
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top ++;

	// Step 3. Push element.
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}// Of push


char pop(CharStackPtr paraStackPtr) {
    // Step 1. Space check.
    if (paraStackPtr->top < 0) {
        printf("Cannot pop element: stack empty.rn");
        return '';
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top --;

	// Step 3. Push element.
    return paraStackPtr->data[paraStackPtr->top + 1];
}// Of pop


void pushPopTest() {
    printf("---- pushPopTest begins. ----rn");

	// Initialize.
    CharStackPtr tempStack = charStackInit();
    printf("After initialization, the stack is: ");
	outputStack(tempStack);

	// Pop.
	for (char ch = 'a'; ch < 'm'; ch ++) {
		printf("Pushing %c.rn", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}//Of for i

	// Pop.
	for (int i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("Pop %c.rn", ch);
		outputStack(tempStack);
	}//Of for i

    printf("---- pushPopTest ends. ----rn");
}// Of pushPopTest


void main() {
	pushPopTest();
}// Of main

括号匹配

这是老师的代码

#include 
#include 

#define STACK_MAX_SIZE 10


typedef struct CharStack {
    int top;

    int data[STACK_MAX_SIZE]; //The maximum length is fixed.
} *CharStackPtr;


void outputStack(CharStackPtr paraStack) {
    for (int i = 0; i <= paraStack->top; i ++) {
        printf("%c ", paraStack->data[i]);
    }// Of for i
    printf("rn");
}// Of outputStack


CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
	resultPtr->top = -1;

	return resultPtr;
}//Of charStackInit


void push(CharStackPtr paraStackPtr, int paraValue) {
    // Step 1. Space check.
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
        printf("Cannot push element: stack full.rn");
        return;
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top ++;

	// Step 3. Push element.
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}// Of push


char pop(CharStackPtr paraStackPtr) {
    // Step 1. Space check.
    if (paraStackPtr->top < 0) {
        printf("Cannot pop element: stack empty.rn");
        return '';
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top --;

	// Step 3. Push element.
    return paraStackPtr->data[paraStackPtr->top + 1];
}// Of pop


void pushPopTest() {
    printf("---- pushPopTest begins. ----rn");

	// Initialize.
    CharStackPtr tempStack = charStackInit();
    printf("After initialization, the stack is: ");
	outputStack(tempStack);

	// Pop.
	for (char ch = 'a'; ch < 'm'; ch ++) {
		printf("Pushing %c.rn", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}//Of for i

	// Pop.
	for (int i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("Pop %c.rn", ch);
		outputStack(tempStack);
	}//Of for i

    printf("---- pushPopTest ends. ----rn");
}// Of pushPopTest


bool bracketMatching(char* paraString, int paraLength) {
	// Step 1. Initialize the stack through pushing a '#' at the bottom.
    CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;

	// Step 2. Process the string.
	for (int i = 0; i < paraLength; i++) {
		tempChar = paraString[i];

		switch (tempChar) {
		case '(':
		case '[':
		case '{':
			push(tempStack, tempChar);
			break;
		case ')':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '(') {
				return false;
			} // Of if
			break;
		case ']':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '[') {
				return false;
			} // Of if
			break;
		case '}':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '{') {
				return false;
			} // Of if
			break;
		default:
			// Do nothing.
			break;
		}// Of switch
	} // Of for i

	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {
		return true;
	} // Of if

	return true;
}// Of bracketMatching


void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}// Of bracketMatchingTest


void main() {
	// pushPopTest();
	bracketMatchingTest();
}// Of main

括号匹配

在一个表达式中含有圆括号或方括号等来表示运算的优先级，将这些括号提取出来就构成了括号序列

例如：表达式[(A+B)*C]-[E-F] 其括号序列为[()][]

合法的括号序列称为匹配序列，不合法的括号序列称为不匹配序列

匹配序列示例：（[()]） [][]() ()[()]

不匹配序列示例：（[()] ][]() (][()]

那么如何判断一个括号序列是否为匹配序列呢？

我们将用栈的结构来进行验证

待判断序列

初始化一个空栈，顺序读入括号
若是右括号则与栈顶元素进行匹配（#若匹配，则弹出栈顶元素并进行下一元素 #若不匹配，则该序列不合法）
若是左括号，则压入栈中
若全部元素遍历完毕，栈中仍然存在元素，则该序列不合法

#define ElemType char
#define MaxSize 50
#include

typedef struct 
{
	ElemType data[MaxSize];
	int top;
}SqStack;

bool StackEmpty(SqStack S)
{
	if (S.top == -1)   //栈空
		return true;
	else
		return false;  //栈不空
}

bool Pop(SqStack& S, ElemType& x)
{
	if (S.top == -1)              //栈空 不能执行出栈操作
		return false;
	x = S.data[S.top];            //先出栈 指针再减1
	S.top--;
	return true;
}

bool Push(SqStack& S, ElemType x)
{
	if (S.top == MaxSize - 1)      //栈满 不能执行入栈操作
		return false;
	S.top++;                      //指针先加1，再入栈
	S.data[S.top] = x;
	return true;
}

bool GetPop(SqStack S, ElemType& x)
{
	if (S.top == -1)            //栈空报错
		return false;
	x = S.data[S.top];          //用x存储栈顶元素
	return true;
}

void initStack(SqStack& S)
{
	S.top = -1;   //初始化栈顶指针
}

int main()
{
	SqStack S;
	initStack(S);
	char sequence[] = { '[','(',')',']','[',']' };
	char* p = sequence;
	while (*p == '')
	{
		if (*p == '(' || *p=='[')
		{
			Push(S, *p);
			p++;
		}
		else
		{
			char getpop;
			GetPop(S,getpop);
			if ((getpop=='('&&*p==')')||(getpop == '[' && *p == ']'))    //判断是否匹配
			{
				char pop;
				Pop(S, pop);
				p++;
			}
			else
			{
				printf("该序列不合法！");
				return 0;
			}
		}
	}
	if (StackEmpty(S))              //判断最后栈是否为空
		printf("该序列合法！");
	else
		printf("该序列不合法！");
	return 0;
}

表达式求值

老师的代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

stack num;
stack op;

void eval()
{
    auto b = num.top();
    num.pop();
    auto a = num.top();
    num.pop();
    auto c = op.top();
    op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

数据结构 栈，括号匹配，表达式求值

C/C++/C#相关栏目本月热门文章

数据结构栈，括号匹配，表达式求值