c++ - 问题 C++ 逆波兰表示法计算器
问题描述
我对 RPN 有疑问。我希望程序在按 ENTER 后完成输入字符,但有些东西不起作用,因为它没有写入 vec。 我试图解决这个任务: 应该确定以逆波兰表示法记录的表达式的值。该表达式将包含以下运算符:+、-、* 和 /(整数除法)和不大于一百万的自然数。结果是 int 类型。
入口 在第一行也是唯一一行,用逆波兰表示法写成的短语。运算符与数字之间用空格字符分隔。表达式长度小于 1000 个字符。
退出 ONP 表达式的结束值。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int RPN(vector<string> ¬ation) {
stack<int> s;
for (string str : notation) {
if (str == "+" or str == "-" or str == "/" or str == "*") {
int a = s.top();
s.pop();
int b = s.top();
s.pop();
if (str == "-") {
s.push(b - a);
continue;
}
if (str == "+") {
s.push(b + a);
continue;
}
if (str == "/") {
s.push(b / a);
continue;
}
if (str == "*") {
s.push(b * a);
continue;
}
} else
s.push(stoi(str));
}
return s.top();
}
int main() {
vector<string> notation;
while (true) {
string sign;
cin >> sign;
if (cin.get() != 'n') {
break;
} else {
notation.push_back(sign);
}
}
for (auto i : notation) // test, print vec
{
cout << i << endl;
;
}
cout << RPN(notation) << endl;
return 0;
}
解决方案
您的代码不保持优先级。它处理加法的方式与处理乘法的方式相同。如果这是您想要的,您可以从左到右执行每个操作。
我想你的程序的目标是有一些优先级并在加法之前执行例如乘法。
这是一个保持优先级的简单代码。该代码假定输入始终正确,并且为简单起见不处理括号。
#include <iostream>
#include <vector>
#include <stack>
int getPrecedence(std::string &o)
{
if (o == "+" || o == "-")
return 1;
return 2;
}
int calculate(int a, int b, const std::string &operation)
{
if (operation == "+")
return a + b;
if (operation == "-")
return a - b;
if (operation == "*")
return a * b;
if (operation == "/")
return a / b;
return -1;
}
void performOperation(std::stack<int> &numbers, std::stack<std::string> &operators) {
int n1 = numbers.top();
numbers.pop();
int n2 = numbers.top();
numbers.pop();
std::string op = operators.top();
operators.pop();
numbers.push(calculate(n2, n1, op));
}
int RPN(std::vector<std::string> ¬ation) {
std::stack<int> numbers;
std::stack<std::string> operators;
if (notation.empty())
return 0;
numbers.push(stoi(notation[0]));
for (int i = 1; i < notation.size(); i+=2)
{
while (!operators.empty() && getPrecedence(operators.top()) >= getPrecedence(notation[i]))
performOperation(numbers, operators);
numbers.push(std::stoi(notation[i+1]));
operators.push(notation[i]);
}
while (!operators.empty())
performOperation(numbers, operators);
return numbers.top();
}
std::vector<std::string> parse(const std::string& input)
{
std::vector<std::string> vec;
std::string current;
for (char c : input)
{
if (isdigit(c))
current += c;
else if (c)
{
if (!current.empty())
{
vec.emplace_back(std::move(current));
current = "";
}
if (c != ' ')
vec.emplace_back(1, c);
}
}
if (!current.empty())
vec.push_back(std::move(current));
return vec;
}
int main() {
// This program doesn't validate input.
// It assumes that the input is always correct.
std::string input;
std::getline(std::cin, input);
std::vector<std::string> notation = parse(input);
std::cout << RPN(notation) << '\n';
}
输入:
1 + 2 + 3 * 3 + 3 / 3 + 5 - 4
输出:
14
为简单起见,我采用程序在输入之前将读取的字符串数。
更新:
上面的代码假设输入是一个infix
表达式。如果输入已经在 中RPN
,则代码将如下所示:
#include <iostream>
#include <vector>
#include <stack>
int calculate(int a, int b, const std::string &operation)
{
if (operation == "+")
return a + b;
if (operation == "-")
return a - b;
if (operation == "*")
return a * b;
if (operation == "/")
return a / b;
return -1;
}
bool isOperation(const std::string& op)
{
return op == "+" || op == "-" || op == "*" || op == "/";
}
int RPN(std::vector<std::string> ¬ation) {
std::stack<int> numbers;
for (const auto& str : notation)
{
if (isOperation(str))
{
int n2 = numbers.top(); numbers.pop();
int n1 = numbers.top(); numbers.pop();
numbers.push(calculate(n1, n2, str));
}
else
numbers.push(std::stoi(str));
}
return numbers.top();
}
std::vector<std::string> parse(const std::string& input)
{
std::vector<std::string> vec;
std::string current;
for (char c : input)
{
if (isdigit(c))
current += c;
else if (c)
{
if (!current.empty())
{
vec.emplace_back(std::move(current));
current = "";
}
if (c != ' ')
vec.emplace_back(1, c);
}
}
if (!current.empty())
vec.push_back(std::move(current));
return vec;
}
int main() {
// This program doesn't validate input.
// It assumes that the input is always correct.
std::string input;
std::getline(std::cin, input);
std::vector<std::string> notation = parse(input);
std::cout << RPN(notation) << '\n';
}
推荐阅读
- excel - sumifs- 有 4 个标准,不包括出现在总和范围内的负值。我试图粘贴下面公式的图像
- javascript - 有没有办法编辑此代码以添加导航并使用箭头滑动动画?
- r - 如何在 Shiny selectInput() 中手动排序选定的值
- vector - 在按值获取 self 的方法调用中是否有更短的附加到向量的方法?
- django - Django如何搜索字段是否为ForeignKey?
- pyspark - 将镶木地板文件读入数据框时如何为文件夹结构指定架构
- drools - 是错误吗?Optaplanner 无法删除 ConstraintMatch
- c++ - C++ boost asio 奇怪的缓冲区溢出
- r - 根据条件用自己的值填充 R 数据表
- r - 如何通过 R 中另一行中满足的条件选择一行?