I have a problem with RPN. I want the program to finish entering characters after pressing ENTER but something doesn't work because it doesn't write to vec. I tried to solve the task: The value of the expression recorded in Reverse Polish Notation should be determined. The expression will contain the following operators: +, -, * and / (integer division) and natural numbers not greater than one million. The result is in the type int.
Entrance In the first and only line the phrase written in Reverse Polish Notation. Operators are separated from numbers by a space character. Expression length is less than 1000 characters.
Exit The end value of the ONP expression.
#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;
}
Your code doesn't maintain precedence. It treats addition the same way it treats multiplication. If that's what you want, you can just perform each operation from left to right.
I suppose the goal of your program is to have some precedence and to perform for example multiplication before addition.
Here is a simple code that maintains precedence. The code assumes that the input is always correct and do not handle parentheses for simplicity.
#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';
}
Input:
1 + 2 + 3 * 3 + 3 / 3 + 5 - 4
Output:
14
For simplicity, I take the number of strings that the program will read before taking the input.
Update:
The above code assumes that the input is an infix expression. If the input is already in the RPN, the code would be like this:
#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';
}