使用栈求表达式的值【数据结构】

中缀表达式转后缀表达式

转换流程：

• 初始化一个运算符栈。
• 自左向右扫描中缀表达式，当扫描到操作数时直接连接到后缀表达式上。
• 当扫描到操作符时，和运算符栈栈顶的操作符进行比较。如果比栈顶运算符高，则入栈。如果比栈顶运算符低或等于，则把栈顶的运算符出栈后连接到后缀表达式上。
• 若运算符是右括号，栈顶是左括号时，删除栈顶运算符（清除括号。后缀表达式中是没有括号的，操作数后面的运算符的优先级由左向右降低）。
• 重复以上过程直到遇到结束符。

求解后缀表达式

后缀表达式的求解流程：

• 创建一个栈。
• 把后缀表达式当成一个字符串，对字符串进行逐字符扫描。
• 遇到操作数入栈，遇到运算符则从栈中取出 2 个操作数，运算后把结果压入栈。
• 重复上述过程，直到扫描结束。则栈中的值为最终结果。

E. DS堆栈–表达式计算

题目描述

计算一个表达式的运算结果

使用C++自带stack堆栈对象来实现

参考课本的算法伪代码P53-54

例如

1. Push (OPTR, ‘#’);表示把字符#压入堆栈OPTR中，转换成c++代码就是OPTR.push(‘#’);
2. Pop(OPND, a); 表示弹出栈OPND的栈顶元素，并把栈顶元素放入变量a中。因此改成c++代码是两个操作：
   a = OPND.top(); OPND.pop();
3. a = GetTop(OPND)表示获取栈OPND的栈顶元素，转成c++代码就是： a = OPND.top();

输入
第一个输入t，表示有t个实例
第二行起，每行输入一个表达式，每个表达式末尾带#表示结束

输入t行

输出

每行输出一个表达式的计算结果，计算结果用浮点数（含4位小数）的格式表示

用cout控制浮点数输出的小数位数，需要增加一个库文件，并使用fixed和setprecision函数，代码如下：

#include
#include
using namespace std;
int main()
{ double temp = 12.34
cout<<fixed<<setprecision(4)<<temp<<endl;
}
输出结果为12.3400

输入样例1
2
1+2*3-4/5#
(66+(((11+22)*2-33)/3+6)*2)-45.6789#

输出样例1
6.2000
54.3211

#include<iostream>
#include<string>
#include<stack>
#include<vector>
using namespace std;
int main()
{int t;cin >> t;for (int i = 0; i < t; i++){string s;//记录后缀表达式vector<string> v;	cin >> s;int idx = 0;stack<string> sta;//转为后缀表达式while (idx<s.size()){int f=idx;//处理小数while((s[idx] >= '0' && s[idx] <= '9')||s[idx]=='.') idx++;if(idx!=f) v.push_back(s.substr(f,idx-f));if (s[idx] == '+' || s[idx] == '-'){if (sta.empty()){sta.push(s.substr(idx,1));idx++;continue;}if (sta.top() == "("){sta.push(s.substr(idx,1));idx++;continue;}while ((!sta.empty()) && (sta.top() == "+" || sta.top() == "-" || sta.top() == "*" || sta.top() == "/")){v.push_back(sta.top());sta.pop();}sta.push(s.substr(idx,1));idx++;}else if (s[idx] == '*' || s[idx] == '/'){if (sta.empty()){sta.push(s.substr(idx,1));idx++;continue;}if (sta.top() == "("|| sta.top() == "+" || sta.top() == "-"){sta.push(s.substr(idx,1));idx++;continue;}while ((!sta.empty()) && (sta.top() == "*" || sta.top() == "/")){v.push_back(sta.top());sta.pop();}sta.push(s.substr(idx,1));idx++;}else if (s[idx] == '('){sta.push(s.substr(idx,1));idx++;continue;}else if (s[idx] == ')'){while (sta.top() != "("){v.push_back(sta.top());sta.pop();}sta.pop();idx++;}//结束符else if (s[idx] == '#'){while (!sta.empty()){v.push_back(sta.top());sta.pop();}idx++;break;}}//后缀表达式的数值栈stack<float> two;for (int j = 0; j < v.size(); j++){if (v[j]!="+"&&v[j]!="-"&&v[j]!="*"&&v[j]!="/"&&v[j]!="#") two.push(stof(v[j]));else{float d1 = two.top();two.pop();float d2 = two.top();two.pop();if (v[j] == "+"){two.push(d1 + d2);}else if (v[j] == "-"){two.push(d2 - d1);}else if (v[j] == "*"){two.push(d2*d1);}else if (v[j] == "/"){two.push(d2 / d1);}}}printf("%.4f\n", two.top());}return 0;
}