练习9.52：使用stack处理括号化的表达式。当你看到一个左括号，将其记录下来。当你在一个左括号之后看到一个右括号，从stack中pop对象，直至遇到左括号，将左括号也一起弹出栈。然后将一个值（括号内的运算结果）push到栈中，表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。
【出题思路】
本题作为栈数据结构的基本练习有些复杂。原因在于，表达式的解析算法对于编程初学者来说相对复杂。解答本题更多的工作是设计表达式解析的逻辑，栈的操作变为次要地位。
【解答】
如下所示，本题的解答已经较为复杂，但这已是将问题大幅简化之后的解答了。我们假定表达式中只有加、减两种运算，由于所有运算优先级相同，无须进行复杂的优先级判断。由于加、减运算都是左结合，因此，遇到一个数值，直接与之前的运算数进行它们中间的运算即可。唯一的例外是括号，它将改变计算次序--括号里的运算将先于括号前的运算执行。不过，我们可以将它看作“阻断” 了括号前的表达式，将括号内的部分看作一个独立的表达式优先处理，计算结果作为一个运算数参与之前的运算即可。
表达式解析的逻辑大致如下：
1. 读入了 一个运算数V。
a） 若栈空或栈顶是左括号，则v是第一个运算数，直接压栈即可。
b） 否则，v前必须是一个运算符，再之前是另一个运算数v'，从栈顶弹出这两项，将计算结果压栈即可；否则，就抛出一个“缺少运算符”异常。
2. 读入了一个左括号，直接压栈。
3. 读入了一个运算符，
a） 若栈空或栈顶不是一个运算数，则抛出一个“缺少运算数”异常。注意，若运算符之前是一个右括号，之前也已处理完毕，栈顶是其计算结果，仍应该是运算数，不影响此逻辑。
b） 否则，运算符压栈。
4. 读入了一个右括号，
a） 若栈空，表明之前没有与之配对的左括号，抛出“未匹配右括号”异常。
b） 若栈顶是左括号，表明括号对之间无表达式，抛出“空括号”异常。
c） 若栈顶不是运算数，表明括号内缺少一个运算数，抛出一个异常。
d） 弹出此运算数V,若栈空或栈顶不是左括号，仍抛出“未匹配右括号”异常；
否则弹出左括号，把v作为新运算数，执行1中的逻辑。
5. 以上均不是，则出现了非法输入，会在转换为数值时产生异常。
6. 当字符串处理完毕后，判断栈中是否有且仅有一个运算数，若是，此值即为表达式运算结果，输出它；否则，表达式非法。
值得注意的是，为了在栈中保存括号、运算符和运算数三类对象，程序中定义了枚举类型obj_type。栈中每个对象都保存了类型t和数值v （如果t是VAL的话）。
#include<iostream>
#include<string>
#include<deque>
#include<stack>
#include<stdexcept>
using namespace std;
//表示栈中对象的不同类型
enum obj_type {LP, RP, ADD, SUB, VAL};
struct obj {
obj(obj_type type, double val = 0) {
t = type;
v = val;}
obj_type t;
double v;
};
inline void skipws(string &exp, size_t &p)
{
p = exp.find_first_not_of(" ",p);
}
inline void new_val(stack<obj> &so, double v)
{
if(so.empty() || so.top().t == LP) { // 空栈或左括号
so.push(obj(VAL, v));
// cout << "push"" << v << endl;
} else if(so.top().t == ADD || so.top().t == SUB) {
//之前是运算符
obj_type type = so.top().t;
so.pop();
/*if(type == ADD)
cout << "pop +" << endl;
else cout << "pop-" << endl;*/
// cout << "pop" << so.top().v << endl;
//执行加减法
if (type == ADD)
v += so.top().v;
else v = so.top().v - v;
so.pop();
so.push(obj(VAL, v)); // 运算结果压栈
// cout << "push " << v << endl;
} else throw invalid_argument ("缺少运算符");
}
int main()
{
stack<obj> so;
string exp;
size_t p = 0, q;
double v;
cout << "请输入表达式：";
getline(cin, exp);
while(p < exp.size ()) {
skipws (exp, p) ; // 跳过空格
if(exp[p] == '(') { //左括号直接压栈
so.push(obj(LP));
p++;
// cout << "push LP" << endl;
} else if(exp[p] == '+' || exp[p] == '-') {
//新运算符
if(so.empty() || so.top().t != VAL)
//空栈或之前不是运算数
throw invalid_argument("缺少运算数");
if(exp[p] == '+') // 运算符压栈
so.push(obj(ADD));
else so.push (obj(SUB));
p++;
// cout << "push" << exp[p - 1] << endl;
} else if(exp[p] ==')'){ // 右括号
p++;
if(so.empty() ) //之前无配对的左括号
throw invalid_argument ("未匹配右括号");
if(so.top().t == LP) // 一对括号之间无内容
throw invalid_argument ("空括号");
if(so.top().t == VAL) { //正确：括号内运算结果
v = so.top().v;
so.pop();
// cout << "pop LP" << v << endl;
if(so.empty() || so.top().t != LP)
throw invalid_argument ("未匹配右括号");
so.pop();
// cout << "pop LP" << endl;
new_val (so, v) ; //与新运算数逻辑一致
} else //栈顶必定是运算符
throw invalid_argument("缺少运算数");
} else { //应该是运算数
v = stod(exp.substr(p), &q);
p += q;
new_val(so, v);
}
}
if(so.size() != 1 || so.top().t != VAL)
throw invalid_argument("非法表达式");
cout << so.top().v << endl;
return 0;
}
【解答解题思路】
其实，如果不是强制使用栈来手工处理解析过程的数据，我们可以写出一个递 归算法（其实是编译器隐含使用栈为我们保存了相关数据）来解析表达式，会更为 简洁、清晰。
本页共132段，5847个字符，8397 Byte(字节)