2024/11/19日 日志 数据结构实验（2）---栈实现表达式求值、队列应用(蓝桥杯)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAXSIZE 100

typedef struct {
    char data[MAXSIZE];
    int top;
} Stack;

// 栈操作
void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAXSIZE - 1;
}

void push(Stack *s, char c) {
    if (!isFull(s)) {
        s->data[++(s->top)] = c;
    }
}

char pop(Stack *s) {
    if (!isEmpty(s)) {
        return s->data[(s->top)--];
    }
    return '\0'; // 空栈时返回空字符
}

char peek(Stack *s) {
    if (!isEmpty(s)) {
        return s->data[s->top];
    }
    return '\0'; // 空栈时返回空字符
}

// 运算符优先级
int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

// 转换为后缀表达式
int infixToPostfix(const char *infix, char *postfix) {
    Stack s;
    initStack(&s);
    int j = 0;
    int prevWasOperator = 1; // 表示前一个字符是否是运算符
    int openParentheses = 0; // 记录开括号数量

    for (int i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];

        if (isspace(c)) {
            continue; // 跳过空格
        }

        if (isdigit(c)) {
            if (!prevWasOperator) {
                return -2; // 表达式缺操作数
            }
            postfix[j++] = c; // 直接将数字加入后缀表达式
            prevWasOperator = 0; // 当前是操作数
        } else if (c == '(') {
            push(&s, c);
            openParentheses++;
            prevWasOperator = 1; // '('后面可以是操作数
        } else if (c == ')') {
            while (!isEmpty(&s) && peek(&s) != '(') {
                postfix[j++] = pop(&s);
            }
            if (isEmpty(&s)) {
                return -1; // 缺少右括号
            }
            pop(&s); // 弹出 '('
            openParentheses--;
            prevWasOperator = 0; // ')'后面可以是运算符
        } else {
            if (precedence(c) == 0) {
                return -3; // 无效字符
            }
            if (prevWasOperator) {
                return -2; // 表达式缺操作数
            }
            while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(c)) {
                postfix[j++] = pop(&s);
            }
            push(&s, c);
            prevWasOperator = 1; // 当前是运算符
        }
    }

    while (!isEmpty(&s)) {
        char top = pop(&s);
        if (top == '(') {
            return -1; // 缺少右括号
        }
        postfix[j++] = top;
    }

    postfix[j] = '\0'; // 结束后缀表达式
    return openParentheses > 0 ? -1 : 0; // 确保所有括号匹配
}

// 计算后缀表达式的值
int evaluatePostfix(const char *postfix) {
    Stack s;
    initStack(&s);
    for (int i = 0; postfix[i] != '\0'; i++) {
        char c = postfix[i];
        if (isdigit(c)) {
            push(&s, c - '0'); // 将字符数字转换为整数
        } else {
            int b = pop(&s);
            int a = pop(&s);
            switch (c) {
                case '+': push(&s, a + b); break;
                case '-': push(&s, a - b); break;
                case '*': push(&s, a * b); break;
                case '/': push(&s, a / b); break;
            }
        }
    }
    return pop(&s); // 返回最终结果
}

int main() {
    char infix[MAXSIZE];
    char postfix[MAXSIZE];

    printf("请输入数学表达式: ");
    fgets(infix, MAXSIZE, stdin);
    
    int result = infixToPostfix(infix, postfix);
    if (result == -1) {
        printf("ERROR:缺少括号\n");
    } else if (result == -2) {
        printf("ERROR:表达式缺操作数\n");
    } else if (result == -3) {
        printf("ERROR:无效字符\n");
    } else {
        printf("后缀表达式: %s\n", postfix);
        int value = evaluatePostfix(postfix);
        printf("结果: %d\n", value);
    }

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MAXM = 1005;
int M;
string inflx[MAXM];
vector<string>post;
queue<string> vip;
queue<string> nor;

void queueup(const string *inflx) {
    for (int i = 1; i <= M; i++) {
        string in = inflx[i];
        if (in.substr(0, 3) == "IN ") {
            string name = in.substr(3);
            char type = name.back();
            name.pop_back(); //删除末尾类型
            name.pop_back();//删除空格
            if (type == 'V') {
                vip.push(name);
            }
            else if (type == 'N') {
                nor.push(name);
            }
        }else if (in.substr(0, 4) == "OUT ") {
            char type = in[4];
            if (type == 'V' && !vip.empty()) {
                vip.pop();
            }
            else if (type == 'N' &&!nor.empty()) {
                nor.pop();
            }
        }
    }
}


int main() {
    cin >> M;
    cin.ignore();
    for (int i = 1; i <= M; i++) {
        getline(cin, inflx[i]);
    }
    queueup(inflx);
    while (!vip.empty()) {
        post.emplace_back(vip.front());
        vip.pop();
    }
    while (!nor.empty()) {
        post.emplace_back(nor.front());
        nor.pop();
    }
    for (int i = 0; i < post.size(); i++) {
        cout << post[i];
        if (i != post.size() - 1) {
            cout << endl;
        }
    }
    return 0;
}