使用堆栈从Infix转换为Postfix（c）

Question

我目前正在进行一个项目，使用单链表形式的堆栈将后缀转换为内缀。我已经设法将表达式，如ab转换为（a b），但是当表达式变得更长时，如ab cd*-。它不工作。我正在考虑将之前转换的表达式推回到堆栈上，但是堆栈的类型是char，表达式是一个字符串，当我试图将其推回时，它会抱怨。我应该把它作为一个模板吗？如果是的话，我该怎么做？或者还有别的方法来解决这个问题吗？

这是我的密码：

#include "stack.h"

void convert(string expression){
    stack c;
    string post = " ";
    string rightop = "";
    string leftop = "";
    string op = "";

    for (int i = 0; i <= expression.length(); i++){
        c.push(expression[i]);
        c.print();
        if (expression[i] == '*' ||
            expression[i] == '+' ||
            expression[i] == '-' ||
            expression[i] == '/'){
            cout << c.top() << endl;
            leftop = c.top();
            cout << leftop << endl;

            c.pop();

            rightop = c.top();
            cout << rightop << endl;
            c.pop();
            op = c.top();
            cout << op << endl;
            //c.pop();
            post = "(" + leftop + " " + op + " " + rightop + ")";

            cout << post << endl;
        }
        //c.push(post);
    }
}


int main(){   
    string expression;
    cout << " Enter a Post Fix expression: ";    
    getline(cin, expression);    
    convert(expression);    
    return 0;
}

Answer 1

我得到的印象是你的“堆栈”没有正确使用。e、 g.如果将ab*推到堆栈上，则变量变为leftop=，rightop=b，op=a，为了转换后缀表达式，最简单的方法是创建一个二元求值树以获得正确的运算符优先级

例如

对于ab c*你想要的

     *
    / \
   +   c
  / \
 a   b 

然后递归或不递归地计算树。每次运算符在它周围使用括号，

Answer 2

原始代码缺少以下要编译的声明：

#include "stack"
#include "string"
#include "iostream"

using namespace std;

接下来，堆栈的类型应该是一个字符串，以便能够在其中存储完整的表达式。

您没有按照正确的顺序从堆栈中获取元素：它首先是op，然后是右上角，最后是leftop

当前注释掉的最后一个c.pop（）是从堆栈中删除第三个元素所必需的，但是它必须在循环内部跟随（再次注释掉）c.push（post）；

表达式上的循环走得太远了：它应该是（int i=0； i

完成此操作后，就足以使convert函数将最后一个post作为字符串返回，以便程序给出预期结果。

正如您在另一个问题中所问的那样，忽略输入字符串中的空格会好得多：您应该在之后立即添加if（isspace（表达式[i]））；for。

通过所有这些修复，代码可能是：

#include <stack>
#include <string>
#include <iostream>
#include <cctypes>

using namespace std;

string convert(string expression){

    stack<string> c;

    string post =" ";
    string rightop="";
    string leftop="";
    string op ="";

    for (int i =0; i<expression.length();i++){
        if (isspace(expression[i])) continue;
        c.push(string(expression.c_str() + i, 1));
        //c.print();
        if(expression[i] == '*' ||
            expression[i] == '+' ||
            expression[i] == '-' ||
            expression[i] == '/'){
                cout<<c.top()<<endl;
                op=c.top();
                cout<<leftop<<endl;

                c.pop();


                rightop=c.top();
                cout<<rightop<<endl;
                c.pop();
                leftop=c.top();
                cout<<op<<endl;
                c.pop();
                post="(" + leftop + " " + op + " " + rightop + ")";

                cout<<post<<endl;
                c.push(post);
        }
    }
    return post;
}

int main(){

    string expression;
    cout<<" Enter a Post Fix expression: ";

    getline(cin,expression);

    string converted = convert(expression);

    cout << "Converted expression : " << converted << endl;

    return 0;
}

当给定ab cd*-时，你会在末尾得到（（a b）-（c*d））

你只需要注释掉所有的跟踪表单转换方法；-）