0

我的任务是编写一个用于我的最终项目（计算器）的 Shutting-Yard 算法。我以对我有意义的方式编写了程序，但是，在调用主算法函数（toRPN）时我没有得到任何输出。我相信这是在 parse 和 toRPN 之间传递值的问题，因为我已经直接在 main 中测试了 parse 并且它工作正常，但是当我尝试在 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_H


class 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

cp:

#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 循环：

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]) 是问题。特别是在 stack1.top() 上运行 getPrecedence。这个函数基本上接受一个字符串并将其与包含所有存储的运算符。当它找到索引时，它返回该索引处的优先级（它们按顺序设置所有索引）。我不明白为什么我不能以这种方式调用这个函数。 stack1.top() 只会给出一个字符串，它会被传递并比较。有什么想法吗？

4

1 回答 1

0

弄清楚了。有一些事情发生了，但困扰程序的主要事情是我在不应该的时候从堆栈中弹出东西，导致堆栈为空，所以它永远不会进入

while (getPrecedence(stack1.top()) > getPrecedence(tokens[i]) || (getPrecedence(stack1.top()) == getPrecedence(tokens[i]) &&
                getAssociativity(tokens[i]) == 'L') && stack1.top() != "(")
于 2018-03-20T15:11:52.730 回答