pta题库答案数据结构

### 关于PTA题库中数据结构的答案解析

#### 中缀表达式转换为后缀表达式的实现方法

对于将中缀表达式转换为后缀表达式的任务，可以采用栈来辅助完成这一过程。具体来说，遍历输入的中缀表达式字符串，遇到操作数则直接加入到输出序列；当碰到运算符时，则需将其与栈顶元素比较优先级，只有当前运算符的优先级高于栈顶运算符时才入栈，否则应先弹出栈内的高优先级运算符直到满足条件再压入新读取的操作符[^1]。

#include<iostream>
#include<stack>
using namespace std;

bool isOperator(char c){
    return (!isdigit(c)&&!isalpha(c));
}

int getPriority(char op){
    if(op=='+'||op=='-')return 1;
    else if(op=='*'||op=='/')return 2;
    return 0;
}

void infixToPostfix(string exp){
    stack<char> operators;
    string output = "";
    
    for(int i=0;i<exp.length();i++){
        // 如果是字母或数字, 添加到结果串
        if(isalnum(exp[i]))output += exp[i];
        
        // 左括号直接入栈
        else if (exp[i]=='(')operators.push('(');
        
        // 遇右括号就一直pop直到遇见左括号
        else if(exp[i]==')'){
            while(!operators.empty() && operators.top()!='('){
                output += operators.top();
                operators.pop();
            }
            operators.pop(); // pop '(' from the stack
        }

        // 当前字符为算术运算符的情况处理
        else{
            while(!operators.empty()&&getPriority(operators.top())>=getPriority(exp[i])){
                output+=operators.top();
                operators.pop();
            }
            operators.push(exp[i]);
        }
    }
    
    // 将剩余的运算符全部加到结果后面
    while(!operators.empty()){
        output += operators.top();
        operators.pop();
    }
    
    cout << "后缀表达式：" << output << endl;
}

此代码片段展示了如何利用栈的数据结构特点解决中缀转后缀的问题，通过合理控制进出栈顺序实现了预期功能。