将算数表达式转换为逆波兰式的C++代码
时间: 2024-03-13 19:46:14 浏览: 29
以下是将中缀算数表达式转换为逆波兰式的C++代码:
```c++
#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
bool is_operator(const string& token) {
return token == "+" || token == "-" || token == "*" || token == "/";
}
int precedence(const string& token) {
if (token == "+" || token == "-") {
return 1;
} else if (token == "*" || token == "/") {
return 2;
} else {
return 0;
}
}
vector<string> infix_to_postfix(const vector<string>& infix) {
stack<string> s;
vector<string> postfix;
for (const auto& token : infix) {
if (is_operator(token)) {
while (!s.empty() && is_operator(s.top()) && precedence(token) <= precedence(s.top())) {
postfix.push_back(s.top());
s.pop();
}
s.push(token);
} else if (token == "(") {
s.push(token);
} else if (token == ")") {
while (!s.empty() && s.top() != "(") {
postfix.push_back(s.top());
s.pop();
}
s.pop();
} else {
postfix.push_back(token);
}
}
while (!s.empty()) {
postfix.push_back(s.top());
s.pop();
}
return postfix;
}
int evaluate_postfix(const vector<string>& postfix) {
stack<int> s;
for (const auto& token : postfix) {
if (is_operator(token)) {
int b = s.top();
s.pop();
int a = s.top();
s.pop();
if (token == "+") {
s.push(a + b);
} else if (token == "-") {
s.push(a - b);
} else if (token == "*") {
s.push(a * b);
} else {
s.push(a / b);
}
} else {
stringstream ss(token);
int x;
ss >> x;
s.push(x);
}
}
return s.top();
}
int main() {
// 中缀表达式: (3+4)*5-6/2
vector<string> infix = {"(", "3", "+", "4", ")", "*", "5", "-", "6", "/", "2"};
vector<string> postfix = infix_to_postfix(infix);
for (const auto& token : postfix) {
cout << token << " ";
}
cout << endl;
int result = evaluate_postfix(postfix);
cout << "Result: " << result << endl;
return 0;
}
```
这个代码使用了 `stack` 来实现算法,其中 `infix_to_postfix` 函数将中缀表达式转换为后缀表达式, `evaluate_postfix` 函数计算后缀表达式的值。在 `main` 函数中,我们使用了 `(3+4)*5-6/2` 这个表达式来测试我们的代码,输出结果为:
```
3 4 + 5 * 6 2 / -
Result: 29
```
这表明我们的代码成功地将中缀表达式转换为了后缀表达式,并正确地计算了表达式的值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)