Пытаюсь реализовать функцию для преобразования строки в обратную польскую запись, но в выходную строки не записываются знаки операций. В чем проблема?
Для преобразования использую следующий алгоритм:
Алгоритм анализирует выражение слева направо.
Если он встречает операнд, он немедленно помещает его в очередь результатов.
Если алгоритм встречает оператор, есть несколько вариантов:
3.1) Если стек операторов пуст, алгоритм помещает входящий оператор в стек.
3.2)Если входящий оператор имеет более высокий приоритет, чем тот оператор, что в настоящее время находится на вершине стека, входящий оператор помещается на вершину стека.
3.3)Если входящий оператор имеет такой же приоритет, верхний оператор извлекается из стека и выводится в очередь, а входящий оператор помещается в стек.
3.4) Если приоритет входящего оператора ниже, верхний оператор извлекается из стека и выводится в очередь, после чего входящий оператор сравнивается с новой вершиной стека.
- Когда все выражение будет проанализировано, все оставшиеся токены перекладываются из стека операторов.
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool is_number(char ch)
{
bool result = false;
if (ch >= '0' && ch <= '9')
result = true;
return result;
}
int prioritet(char ch)
{
int prioritet;
switch (ch)
{
case '*':
case '/':
return 4;
case '-':
case '+':
return 3;
case '(':
return 2;
case ')':
return 1;
}
return 0;
}
string Reverse_Polish_Natation(string input_string)
{
char ch;
string output_string;
stack<char> stek_operator;
for (int i = 0; i < input_string.size(); ++i)
{
ch = input_string[i];
if (is_number(ch) == true)
{
while (is_number(ch) == true)
{
output_string.push_back(ch);
i++;
ch = input_string[i];
}
output_string.push_back(' ');
}
else if (ch == ' ')
{
while (input_string[i] == ' ')
i++;
i--;
}
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
if (stek_operator.empty())
{
stek_operator.push(ch);
}
else if (prioritet(ch) < prioritet(stek_operator.top()))
{
output_string.push_back(stek_operator.top());
stek_operator.pop();
if (prioritet(ch) > prioritet(stek_operator.top()))
{
stek_operator.push(ch);
}
else if (prioritet(ch) == prioritet(stek_operator.top()))
{
output_string.push_back(stek_operator.top());
stek_operator.pop();
stek_operator.push(ch);
}
}
}
}
cout << output_string << endl;
return output_string;
}
int main()
{
string input_string = "5 + 10 * 3";
Reverse_Polish_Natation(input_string);
}
Ответы (2 шт):
Потому что у вас в выходную строку записывается оператор из вершины стека, только если его приоритет больше, чем у входящего prioritet(ch) < prioritet(stek_operator.top()). А условие противного prioritet(ch) > prioritet(stek_operator.top()) находится внутри этого условия и никогда не выполняется.
else if (prioritet(ch) < prioritet(stek_operator.top())) // первое условие
{
output_string.push_back(stek_operator.top());
stek_operator.pop();
if (prioritet(ch) > prioritet(stek_operator.top())) // никогда не выполняется, т.к. находится внутри противоположного
{
stek_operator.push(ch);
}
else if (prioritet(ch) == prioritet(stek_operator.top())) // тоже никогда не выполняется
{
output_string.push_back(stek_operator.top());
stek_operator.pop();
stek_operator.push(ch);
}
}
Ну например можно сделать вот так:
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
while(true)
{
if (stek_operator.empty() || prioritet(ch) > prioritet(stek_operator.top()))
{
stek_operator.push(ch);
break;
}
if (prioritet(ch) == prioritet(stek_operator.top()))
{
output_string.push_back(stek_operator.top());
stek_operator.pop();
stek_operator.push(ch);
break;
}
if (prioritet(ch) < prioritet(stek_operator.top()))
{
output_string.push_back(stek_operator.top());
stek_operator.pop();
}
}
}