Мне поручено написать алгоритм Shunting-Yard для использования в моем конечном проекте (калькулятор). Я написал программу способом, который имеет смысл для меня, однако я не получаю никакого вывода при вызове функции основного алгоритма (toRPN). Я полагаю, что это проблема с передачей значений между parse и toRPN, потому что я тестировал синтаксический анализ непосредственно в main и он работает нормально, но когда я пытаюсь выполнить тест печати в функции toRPN, он ничего не печатает. Может ли кто-нибудь указать мне правильное направление?
Заголовок:
#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
#ifndef SHUNTING_YARD_ALGORITHM_SHUNTINGYARD_H
#define SHUNTING_YARD_ALGORITHM_SHUNTINGYARD_Hclass ShuntingYard {
public:
stack <string> stack;
vector <string> tokens;
queue <string> outputList;
vector <char> operators;
vector <int> precedence;
vector <char> associativity;
ShuntingYard ();
bool hasOnlyDigits(const string s);
int getPrecedence(const string s);
int getAssociativity(const char c);
vector<string> parse(const string input) const;
string mainAlgorithm(const string);
};
#endif //SHUNTING_YARD_ALGORITHM_SHUNTINGYARD_H
каст:
#include "ShuntingYard.h"#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <sstream>
#include <numeric>
using namespace std;
stack <string> stack1;
queue <string> outputList;
vector <string> operators;
vector <int> precedence;
vector <char> associativity;
ShuntingYard::ShuntingYard () = default;
bool hasOnlyDigits(const string s){
return s.find_first_not_of( "0123456789" ) == string::npos;
}
int getPrecedence(const string s) {
for(int i = 0; i < operators.size(); i++) {
if (s == operators[i])
return precedence[i];
}
}
char getAssociativity(const string s) {
for(int i = 0; i < operators.size(); i++) {
if (s == operators[i])
return associativity[i];
}
}
vector<string> parse(const string input) {
// Parses the string by white space
istringstream ss(input);
vector <string> tokenVector;
// Fill vector with ss
for (string input; ss >> input;) {
tokenVector.push_back(input);
}
return tokenVector;
}string toRPN(const string s) {
// Delimit string by white space and store in vector
vector <string> tokens = parse(s);
// Test print
for (int i = 0; i < tokens.size(); i ++)
cout << tokens[i];
//Change "rt" to "$" to be easily accessed
for (int i = 0; i < tokens.size(); i ++) {
if (tokens[i] == "rt")
tokens[i] = "$";
}
// Stores operators and their precedence/associativity to vectors using same index
operators.push_back("+"); precedence.push_back(2); associativity.push_back('L');
operators.push_back("-"); precedence.push_back(2); associativity.push_back('L');
operators.push_back("/"); precedence.push_back(3); associativity.push_back('L');
operators.push_back("*"); precedence.push_back(3); associativity.push_back('L');
operators.push_back("^"); precedence.push_back(4); associativity.push_back('R');
operators.push_back("$"); precedence.push_back(4); associativity.push_back('R');// Shunting-Yard logic
while (tokens.size() != 0) {
for (int i = 0; i < tokens.size(); i++) {
if (hasOnlyDigits(tokens[i]))
outputList.push(tokens[i]);
if ( find(operators.begin(), operators.end(), tokens[i]) != operators.end()) {
while (getPrecedence(stack1.top()) > getPrecedence(tokens[i]) || (getPrecedence(stack1.top()) == getPrecedence(tokens[i]) &&
getAssociativity(tokens[i]) == 'L') && stack1.top() != "(") {
outputList.push(stack1.top());
stack1.pop();
stack1.push(tokens[i]);
}
}
if (tokens[i] == "(")
stack1.push(tokens[i]);
if (tokens[i] == ")")
while(!stack1.empty() && stack1.top() != "(") {
outputList.push(stack1.top());
stack1.pop();
}
stack1.pop();
}
if (tokens.size() == 0) {
while(!stack1.empty()) {
outputList.push(stack1.top());
stack1.pop();
}
}
}
// Replaces values with "$" back to "rt"string str;
while (!outputList.empty()) {
if (outputList.front() == "$") {
str.insert(0,"rt");
outputList.pop();
}
else {
str.insert(0, (outputList.front()));
outputList.pop();
}
}
return str;
}
int main() {
string s1 = "3 + 4";
cout << toRPN(s1);
}
Обновить:
Я сузил проблему до следующего цикла:
while (getPrecedence(stack1.top()) > getPrecedence(tokens[i]) || (getPrecedence(stack1.top()) == getPrecedence(tokens[i]) &&
getAssociativity(tokens[i]) == 'L') && stack1.top() != "(") {
outputList.push(stack1.top());
stack1.pop();
stack1.push(tokens[i]);
}
Проблема в строке getPrecedence (stack1.top ()> getPrecedence (tokens [I]). В частности, запуск getPrecedence в stack1.top (). Эта функция в основном принимает строку и сравнивает ее с вектором, содержащим все сохраненные операторы. Когда он находит индекс, он возвращает приоритет этого индекса (они установлены со всеми индексами по порядку). Я не понимаю, почему я не могу вызвать эту функцию таким образом. stack1.top () просто выдаст строку, которая будет передана и сравнена. Есть мысли?
Догадаться. Было несколько вещей, идущих один, но главное, что преследовало программу, было то, что я выталкивал вещи из стека, когда не должен, в результате чего стек был пустым, поэтому он никогда не попадал в
while (getPrecedence(stack1.top()) > getPrecedence(tokens[i]) || (getPrecedence(stack1.top()) == getPrecedence(tokens[i]) &&
getAssociativity(tokens[i]) == 'L') && stack1.top() != "(")
Других решений пока нет …