c++ - 中缀到后缀转换c++

Question

我正在尝试从中缀转换为后缀，然后评估后缀表达式以获得最终答案。不过，我遇到了一个严重的问题，因为出于某种原因，转换根本不起作用。例如，当我输入第一个中缀表达式:24 + 33 * ( 7 - 5 ) + 8/3 它输出 24 33 7 5 45404243 8 34743 这显然是非常错误的。我不太确定问题出在哪里。下面我已经包含了所有需要的代码。我还必须创建自己的堆栈类，因此如果有帮助，我也会将其包括在内。任何提示将不胜感激!

#include "stacks.h"
#include <iostream>
#include <string>


using namespace std;

bool IsOperand(char C)
{
    if(C >= '0' && C <= '9') return true;
    return false;
}

bool IsOperator(char C)
{
    if(C == '+' || C == '-' || C == '*' || C == '/')
        return true;

    return false;
}
int GetOperatorWeight(char op)
{
    int weight = -1;
    switch(op)
    {
        case '+':
        case '-':
            weight = 1;
        case '*':
        case '/':
            weight = 2;
    }
    return weight;
}

int HasHigherPrecedence(char op1, char op2)
{
    int op1Weight = GetOperatorWeight(op1);
    int op2Weight = GetOperatorWeight(op2);

    return op1Weight > op2Weight ?  true: false;
}

int PerformOperation(char operation, int operand1, int operand2)
{
    if(operation == '+') return operand1 +operand2;
    else if(operation == '-') return operand1 - operand2;
    else if(operation == '*') return operand1 * operand2;
    else if(operation == '/') return operand1 / operand2;

    else cout<<"Unexpected Error \n";
    return -1; 
}

bool IsNumericDigit(char C)
{
    if(C >= '0' && C <= '9') return true;
    return false;
}

int evalPost(string item)
{
    stacks S;

    for(int i = 0;i< item.length();i++) {


        if(item[i] == ' ' || item[i] == ',') continue;

        else if(IsOperator(item[i])) {

            int operand2 = stoi(S.stackTop()); S.pop();
            int operand1 = stoi(S.stackTop()); S.pop();

            int result = PerformOperation(item[i], operand1, operand2);

            S.push(to_string(result));
        }
        else if(IsNumericDigit(item[i]))
        {
            int operand = 0;
            while(i<item.length() && IsNumericDigit(item[i]))
            {
                operand = (operand*10) + (item[i] - '0');
                i++;
            }

            i--;

            S.push(to_string(operand));
        }
    }
    return stoi(S.stackTop());
}



string infToPost(string item)
{
    stacks S;
    string postfix = "";
    for(int i = 0;i< item.length();i++) {
        cout<<postfix<<endl;
        if(item[i] == ' ')
            postfix +=item[i];

        else if(IsOperator(item[i]))
        {

            while(!S.empty() && S.stackTop() != "(" && HasHigherPrecedence(*(S.stackTop().c_str()),item[i]))
            {
                postfix+= S.stackTop();
                S.pop();
            }
            S.push(to_string(item[i]));
            //S.pop();
        }

        else if(IsOperand(item[i]))
        {
            postfix +=item[i];
        }

        else if (item[i] == '(')
        {
            S.push(to_string(item[i]));
        }

        else if(item[i] == ')')
        {
            while(!S.empty() && S.stackTop() !=  "(") {
                postfix += S.stackTop();
                S.pop();
            }
            S.pop();
        }
    }


    while(!S.empty()) {
        postfix += S.stackTop();
        S.pop();
    }

    return postfix;
}

int main()
{
    string selection="";
    string infix;
    string postfix;
    string eval;
    cout<<"***********************************************************"<<endl;
    cout<<"1. Read an expression in infix notation."<<endl;
    cout<<"2. Convert infix to postfix."<<endl;
    cout<<"3. Evaluate the expression using postfix notation."<<endl;
    cout<<"4. Exit"<<endl;
    cout<<"***********************************************************"<<endl;
    cout<<"Select: ";
    getline(cin, selection);
//    cin>>selection;
//    cin.ignore();
    while (selection>"4" || selection<"1")
    {
        cout<< "Please enter a different choice (1-4): ";
        getline(cin, selection);
    }
    while(selection!="4")
    {

        if (selection=="1")
        {
            cout<<"Enter an infix expression: ";
            getline(cin,infix);
            cout<<"\n";
        }

        if(selection=="2")
        {
            cout<<"Infix expression: "<<infix<<endl;
            postfix = infToPost(infix);
            cout<<"Postfix expression: "<<postfix<<endl;
            cout<<"\n";
        }

        if(selection=="3")
        {
            cout<<"Infix expression: "<<infix<<endl;
            eval = evalPost(postfix);
            cout<<"Evaluation of this expression: "<<endl;
            cout<<"\n";
        }

        selection = "";
        cout<<"***********************************************************"<<endl;
        cout<<"1. Read an expression in infix notation."<<endl;
        cout<<"2. Convert infix to postfix."<<endl;
        cout<<"3. Evaluate the expression using postfix notation."<<endl;
        cout<<"4. Exit"<<endl;
        cout<<"***********************************************************"<<endl;
        cout<<"Select: ";
        getline(cin,selection);
        //cin.ignore();
        while (selection>"4" || selection<"1")
        {
            cout<< "Please enter a different choice (1-4): ";
            getline(cin, selection);
        }
    }
    cout<<"Thank you for using my program."<<endl;
    return 0;

}

堆栈类标题

#ifndef __Programming_Assingment_3__stacks__
#define __Programming_Assingment_3__stacks__
#include <string>
#include <vector>
using namespace std;

//define the stacks class
class stacks
{
public:
    //constructor
    stacks();
    //push function
    void push(string item);
    //pop function
    void pop();
    //function to get top of stack
    string stackTop();
    //check if stack is empty
    bool empty();
private:
    //create vector and integer
    int top;
    vector<string> sstack;
};

#endif /* defined(__Programming_Assingment_3__stacks__) */

堆栈类 CPP 文件

#include "stacks.h"
#include <iostream>
#include <string>

using namespace std;

//Contstructor
stacks::stacks()
{
    top = -1;
}

//push the item onto the stack
void stacks::push(string item)
{
    sstack.push_back(item);
    top++;
}

//check if the stack is empty
bool stacks::empty()
{
    if (top==-1)
        return true;
    else
        return false;
}

//delete the last item on the stack
void stacks::pop()
{
    try{
        if (sstack.size()==0) throw 0;
    } catch(int err){
        cout<<"stack is empty."<<endl;
        cout<<"Cannot pop an item."<<endl;
        return;
    }
    sstack.pop_back();
    top--;
}

//get the top of the stack
string stacks::stackTop()
{
    try{
        if (sstack.size()==0) throw 0;
    } catch (int err) {
        cout<< "stack is empty."<<endl;
        return 0;
    }
    return (sstack[top]);
}

Answer 1

当您使用此行将运算符压入堆栈时:

S.push(to_string(item[i]));

to_string 正在获取字符并将其视为整数。这会产生诸如“43”表示“+”和“45”表示“-”的字符串。

取而代之的是，您想要构造一个仅包含该字符的字符串。一种方法是使用带有计数和字符值的字符串构造函数。使用计数 1。

S.push(std::string(1, item[i]));

编辑:这里是 infoToPost 函数的变化。不要更改其他方法中的任何其他 to_string 调用，因为它们仍然是必需的(因为您要将整数值转换为字符串)。

string infToPost(string item)
{
    stacks S;
    string postfix = "";
    for (int i = 0; i< item.length(); i++) {
        cout << postfix << endl;
        if (item[i] == ' ')
            postfix += item[i];

        else if (IsOperator(item[i]))
        {

            while (!S.empty() && S.stackTop() != "(" && HasHigherPrecedence(*(S.stackTop().c_str()), item[i]))
            {
                postfix += S.stackTop();
            S.pop();
            }
            S.push(string(1, item[i]));
            //S.pop();
        }

        else if (IsOperand(item[i]))
        {
            postfix += item[i];
        }

        else if (item[i] == '(')
        {
            S.push(string(1, item[i]));
        }

        else if (item[i] == ')')
        {
            while (!S.empty() && S.stackTop() != "(") {
                postfix += S.stackTop();
                S.pop();
            }
            S.pop();
        }
    }


    while (!S.empty()) {
        postfix += S.stackTop();
        S.pop();
    }

    return postfix;
}