使用堆栈（c ++）从中缀转换为Postfix [英] Converting from Infix to Postfix using stacks (c++)

问题描述

我目前正在开发一个项目，使用堆栈以单链表的形式从后缀转换为中缀。我已经设法将诸如 ab + 的表达式转换为（a + b），但是当表达式变长时 ab + cd * - 。它不工作。我正在考虑将先前转换的表达式推回堆栈，但是堆栈是char类型，表达式是一个字符串，当我尝试推回它时，它抱怨。

I'm currently working on a project to convert from postfix to infix using a stack in the form of a singly linked list. I've managed to convert expressions such as ab+ to (a+b) however when the expression gets longer such as ab+cd*-. It doesn't work. I'm considering pushing the previously converted expression back onto the stack however the stack is of type char and the expression is a string and it complains when I try to push it back. Should I make it a template and if so how would I do it or is there anyway else to solve this problem.

这是我的代码：

#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;
}

推荐答案

堆栈未正确使用。例如如果在栈上推送ab + *，你的变量变成 leftop = + ， rightop = b ， op = a ，为了转换后缀表达式，最容易创建一个二进制评估树以获得运算符优先权

i get the impression your "stack" is not used properly. e.g. if ab+* is pushed on the stack your variables become leftop = +, rightop = b, op = a, in order to convert a postfix expression it is easiest to create a binary evaluation tree to get the operator precedence right

例如

代表您想要的ab + c *

for ab+c* you want

     *
    / \
   +   c
  / \
 a   b 

然后递归地或不递归地评估树。每次运算符是+或 - 使用括号，

and then evaluate the tree either recursively or not. everytime the operator is + or - use parenthesis around it,

这篇关于使用堆栈（c ++）从中缀转换为Postfix的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！