数据结构-C语言代码 day6-栈及其应用_在c语言中栈的实现及应用代码

typedef struct CharStack 
{
    int top;
    int data[STACK_MAX_SIZE]; 
} *CharStackPtr;

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

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

void push(CharStackPtr paraStackPtr, int paraValue)
{
    // 空间检查（是否栈满）
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) 
    {
        printf("堆栈已满，无法添加.\r\n");
        return;
    }
 
    // 顶部更新.
	paraStackPtr->top ++;
 
	// 入栈.
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}

char pop(CharStackPtr paraStackPtr) 
{
    // 空间检查（判断空栈）.
    if (paraStackPtr->top < 0) 
    {
        printf("堆栈为空，无法弹出.\r\n");
        return '\0';
    }
 
    // 顶部更新.
	paraStackPtr->top --;
 
    return paraStackPtr->data[paraStackPtr->top + 1];
}

void pushPopTest() 
{
    printf("栈的进出开始测试：\r\n");
 
	// 初始化
    CharStackPtr tempStack = charStackInit();
    printf("初始化后的栈: ");
	outputStack(tempStack);
 
	// 压栈
	for (char ch = 'a'; ch < 'n'; ch ++) 
    {
		printf("添加 %c.\r\n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}//Of for i
 
	// 弹栈
	for (int i = 0; i < 4; i ++) 
    {
		char ch = pop(tempStack);
		printf("删除 %c.\r\n", ch);
		outputStack(tempStack);
	}
 
    printf("测试结束\r\n");
}

栈的进出开始测试：
初始化后的栈:
添加 a.
a
添加 b.
a b
添加 c.
a b c
添加 d.
a b c d
添加 e.
a b c d e
添加 f.
a b c d e f
添加 g.
a b c d e f g
添加 h.
a b c d e f g h
添加 i.
a b c d e f g h i
添加 j.
a b c d e f g h i j
添加 k.
堆栈已满，无法添加.
a b c d e f g h i j
添加 l.
堆栈已满，无法添加.
a b c d e f g h i j
添加 m.
堆栈已满，无法添加.
a b c d e f g h i j
删除 j.
a b c d e f g h i
删除 i.
a b c d e f g h
删除 h.
a b c d e f g
删除 g.
a b c d e f
测试结束

bool bracketMatching(char* paraString, int paraLength) 
{
	// 通过在底部压入“#”来初始化堆栈
    CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;
 
	// 处理字符串
	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;
			}
			break;
		case ']':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '[') {
				return false;
			}			break;
		case '}':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '{') {
				return false;
			}
			break;
		default:
			break;
		}
	}
 
	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') 
    {
		return true;
	}
 
	return true;
}

void bracketMatchingTest() 
{
    printf("括号匹配测试开始：\r\n");
	char* tempExpression = "{6+3-[1+2*(6-2)]}/2";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("'%s'是否括号匹配? %d \r\n", tempExpression, tempMatch);
 
 
	tempExpression = "[1+2*8)(]";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("'%s'是否括号匹配? %d \r\n", tempExpression, tempMatch);
 
	tempExpression = "({[]})";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("'%s'是否括号匹配? %d \r\n", tempExpression, tempMatch);
 
	tempExpression = "()()[]";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("'%s'是否括号匹配? %d \r\n", tempExpression, tempMatch);
 
 
	tempExpression = "{]()";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("'%s'是否括号匹配? %d \r\n", tempExpression, tempMatch);
    printf("测试结束\r\n");
}

括号匹配测试开始：
'{6+3-[1+2*(6-2)]}/2'是否括号匹配? 1
'[1+2*8)(]'是否括号匹配? 1
'({[]})'是否括号匹配? 1
'()()[]'是否括号匹配? 1
'{]()'是否括号匹配? 0
测试结束

//202031061018 刘知鑫
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
 
using namespace std;
 
stack<int> num;
stack<char> 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<char, int> 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;
}