每日科普 · 2026-10-21 周三

考研 408 × 求职面试

知识点 · 数据结构 · 进阶

栈在表达式求值与括号匹配中的应用

栈的核心是后进先出，适合处理最近的、尚未完成的事情。
括号匹配：从左到右扫描，遇左括号就入栈；遇右括号先看栈顶是否为同类左括号，是则弹出，否则不匹配；扫描结束栈必须为空。栈顶就是当前最急切等待配对的左括号。
表达式求值：中缀转后缀时，操作数直接输出，运算符按优先级进出栈，遇右括号弹出到左括号；后缀求值时，遇操作数入栈，遇运算符弹出两个数计算，再把结果压回。
两者本质相同：用栈保存待匹配括号或待处理运算符，保证最近进入的最先处理。常见易错点是右括号到来时栈空、括号类型不匹配、表达式结束后栈中仍有运算符或左括号，以及运算符优先级和左结合处理错误。

每日一题 · 数据结构

栈在表达式求值与括号匹配中的应用

将中缀表达式 A+B*(C-D) 转换为后缀表达式（逆波兰式），写出结果。

解析

结果为 A B C D - * +。扫描：A输出；+入栈；B输出；*优先级高于+，入栈；左括号入栈；C输出；-入栈；D输出；遇右括号，弹出-并输出，再弹出左括号；到末尾依次弹出*和+。故得到 A B C D - * +。关键是运算符按优先级弹栈，右括号只弹出到左括号。

面试小贴士 · 数据结构

栈在表达式求值与括号匹配中的应用

面试常问手写括号匹配、中缀转后缀或后缀求值。先讲栈的后进先出和规则，再写代码；别忽略栈空、括号类型、优先级与左结合。遇到右括号先判空，最后检查残留左括号。

代码实现 · C++

代码示例

#include <iostream>
#include <stack>
#include <string>
using namespace std;
// 括号匹配：左括号入栈，右括号校验栈顶
bool check(const string &s){
    stack<char> st;
    for(char c:s){
        if(c=='('||c=='['||c=='{') st.push(c);
        else if(c==')'||c==']'||c=='}'){
            if(st.empty()) return false;
            char t=st.top(); st.pop();
            if((c==')'&&t!='(')||(c==']'&&t!='[')||(c=='}'&&t!='{')) return false;
        }
    }
    return st.empty();
}
int main(){
    string s; cin>>s;
    cout<<(check(s)?"Yes":"No")<<endl;
    return 0;
}