C++ Infix to Postfix 适用于某些输入但不适用于其他输入？

Question

我昨晚问了一个关于计算机科学类(class)的问题，我必须在其中将中缀转换为后缀表示法并进行评估。我能够调试它并使其正常工作(某种程度上)，但是，对于某些表达式，我仍然会得到奇怪的输出。

它适用于基本输入(例如 7+7、3+2 等)的第一次迭代...但是，一旦您添加括号或其他表达式，它就会变得异常，我无法弄清楚为什么。

下面是代码以及我得到的文本文件/输出。

头文件:

#ifndef STACK_H
#define STACK_H
/////////////////////////////////////////////////////
////Includes/////////////////////////////////////////
/////////////////////////////////////////////////////
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <stdlib.h>
#include <iomanip>
#include <sstream>
#include <stdio.h>
/////////////////////////////////////////////////////
using namespace std;

/*-------------------------------------------------------------------------------------------------------------*/
template <typename Object>
class Stack
{
private:
    class stackListNode
        {
        public:
            Object data;
            stackListNode *next;
        private:
            //Nothing to declare-->placeholder since class 
            //sets data members to private initially
        };

    stackListNode *top;

public:
    /////////////////////////////////////////////////
    //Constructor Function//////////////////////////
    Stack() {top = NULL;}

        /////////////////////////////////////////////////
        //Rest of functions defined inline for simplicity

        void push(char token)   // Push token onto the stack and create new node for top of stack
            {
                stackListNode *newNode = new stackListNode;
                newNode->data = token;
                newNode->next = top;
                top = newNode;
            }

        char pop()
            {
                if(empty())
                {
                    cout << "Stack is empty!\n" << endl;
                    return NULL;                
                }

                stackListNode *temp = top;
                top = temp->next;
                return temp->data;
            }

        char peek()
            {
                if(empty())
                {
                    cout << "Stack is empty!\n" << endl;
                    //exit(1);
                    return NULL;                
                }
                return top->data;
            }

        int empty()
            {
                return top == NULL;
            }
};

#endif  

司机:

/////////////////////////////////////////////////////
////Includes/////////////////////////////////////////
/////////////////////////////////////////////////////
#include <iostream>
#include <fstream>
#include <string>
#include "Stack.h"
/////////////////////////////////////////////////////
using namespace std;

int precendence(char stack_beginning); //overloaded for character sitting at the front of the stack
void InFixToPostfix(ifstream& in_file);
//double EvaluatePostfix(double first_operand, double second_operand, char*myArray);

int main()
{
////VARS/////////////////////////////////////////////

    string absolutePath;

    cout << endl;
    cout << "Please type in the name of the file you would to open \n";
    cin >> absolutePath;

    ifstream in_file;
    in_file.open(absolutePath.c_str());
    if(!in_file)
    {
        cout << "failed to open input file\n" ;
        return 1 ;
    }
    else
    {
        InFixToPostfix(in_file); //kicks off program
    }

}

void InFixToPostfix(ifstream& in_file)
{
    string infix;
    int right_parentheses = 0;
    int left_parentheses = 0;

    while(getline(in_file, infix))
    {
        char myArray[infix.length()];
        strcpy(myArray, infix.c_str());


        ////////Declares a STRING Stack////////////////////////////////
        Stack<char> stack_string;
        ////////Declares an Int Stack/////////////////////////////////
        Stack<double> stack_int;
        //////////////////////////////////////////////////////////////
        int j = 0;
        char *postfix = new char[infix.length()];
        for(int i = 0; i < sizeof(myArray); i++)
        {
            int number = myArray[i] - '0';
            if(number > 0)
            {
                postfix[j] = myArray[i];
                j++;
                //outputs the number b/c it is an operand
            }
            else if(myArray[i] == ')')
            {
                while(stack_string.peek() != '(')
                {
                    cout << stack_string.peek() << " ";
                    stack_string.pop(); //pops to the peek
                }
            stack_string.pop(); // if there is a ), pops to the peek
            }
            else if(myArray[i] == '+' || myArray[i] == '-' || myArray[i] == '/' || myArray[i] == '*' || myArray[i] == '(')
            {
                if(!stack_string.empty())
                    {
                        char stack_beginning = stack_string.peek();
                        int stack_top = precendence(stack_beginning);
                        //int stack_top = precendence(stack_string.peek());
                        int operatorHierarchy = precendence(myArray[i]);
                        //must be declared here because i will have been interated through array
                        while(operatorHierarchy >= stack_top)
                        {
                            stack_string.pop();
                            postfix[j] = myArray[i];
                            j++;
                            stack_top = precendence(stack_beginning);
                            operatorHierarchy = precendence(myArray[i]);
                        }
                    }
                stack_string.push(myArray[i]);
            }
        }
        while(!stack_string.empty())
        {
           char c = (char)stack_string.pop();
           postfix[j] = c;
           j++;

        }

        //////////Evaluate Section/////////////////////////////
        cout << postfix <<endl;
        for(int i = 0; i < j; i++)
        {
            //cout<<myArray[i]<<endl;
            cout << postfix[i] <<endl;
            int number = postfix[i] - '0';
            if(number > 0) //this is a number
            {
                stack_int.push(number);
                cout << stack_int.peek();
            }
            else if(postfix[i] == '*' || postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '/')
            {
                double first_operand;
                first_operand = stack_int.peek(); //fetches first operand on the stack_int
                stack_int.pop();
                //////////////////
                double second_operand;
                second_operand = stack_int.peek();
                stack_int.pop();
                //////////////////
                if(postfix[i] == '+')
                {
                    stack_int.push(second_operand + first_operand);
                }
                else if(postfix[i] == '-')
                {
                    stack_int.push(second_operand - first_operand);
                }
                else if(postfix[i] == '*')
                {
                    stack_int.push(second_operand * first_operand);
                }
                else if(postfix[i] == '/')
                {
                    stack_int.push(second_operand / first_operand);
                }
            }
        }
    cout << (double)stack_int.pop() << endl;
    }
}

int precendence(char stack_beginning)
{
    int precendence;
    if(stack_beginning == '(')
    {
        precendence = 3;
        return precendence;
    }
    else if(stack_beginning == '*' || stack_beginning == '/')
    {
        precendence = 2;
        return precendence;
    }
    //by making it 2, the precendence is dubbed less than +/-
    else if(stack_beginning == '+' || stack_beginning == '-')
    {
        precendence = 1;
        return precendence;
    }
    else
    {
        return 0;
    }
}    //by making it 1, the precendence is dubbed greater than */"/"

文本文件:

9+5
(4+2)
(3+8)/2

输出:

Please type in the name of the file you would to open 
f.txt
95+
9
    5
+
14
+ 42
4
2
2
+ 382/
3
8
2
/
4

Answer 1

以下是我发现的一些问题:

C-Style 字符串或 std::string，不能同时使用
您正在使用 strcpy与 std::string::c_str() .坚持 std::string .
您可以通过将其视为数组来访问单个字符，string[5] 返回第 6 个字符。

字符堆栈不同于字符串堆栈
你的评论说了一堆字符串，但你却声明了 Stack<char>这是一堆字符，而不是字符串。
同样，Stack 也不是整数的堆栈。
当您应该坚持使用 std::string 的变量时，您正在动态分配数组的字符。 .

使用库函数。
参见 isdigit和 toupper和 tolower .

使用调试器
现在是使用调试器的好时机。单步执行程序并查看变量。

使用打印语句
如果您拒绝使用调试器，请在您的代码中放置带有行号的“打印”语句，以获取程序行为的快照。