Stack Infix to Prefix 无法正常工作

Question

我有一个任务要编写一个程序，在 C++ 中将中缀转换为前缀。我已经编写了一个代码来这样做，但问题是我只得到操作数而不是最终结果中的运算符。我已经检查了很多次我的代码，干运行它，但我找不到问题。这是代码：

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int Prec(char c)
{
    if(c == '^')
    {
        return 3;
    }
    
    else if(c == '*' || c == '/')
    {
        return 2;
    }
    
    else if(c == '+' || c == '-')
    {
        return 1;
    }
    
    else 
    {
        return -1;
    }
} // prec

string InfixToPrefix(string s)
{
    reverse(s.begin(), s.end());
    
    stack<char> st;
    string res;
    
    for(int i=0; i<s.length(); i++)
    {
        if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
        {
            res += s[i];
        }
        
        else if(s[i] == ')')
        {
            st.push(s[i]);
        }
        
        else if(s[i] == '(')
        {
            while(!st.empty() && st.top() != ')')
            {
                res += st.top();
                st.pop();
            }
            
            if(!st.empty())
            {
                st.pop();
            }
            
            else
            {
                while(!st.empty() && Prec(st.top()) >= Prec(s[i]))
                {
                    res += st.top();
                    st.pop();
                }
                
                st.push(s[i]);
            }
        }
    } // for loop
    
    while(!st.empty())
    {
        res+=st.top();
        st.pop();
    }
    
    reverse(res.begin(), res.end());
    
    return res;
} // InfixToPrefix()

int main()
{
    cout<<InfixToPrefix("(a-b/c)*(a/k-l)")<<endl;
}

有人可以帮忙吗？
正确的输出应该是“*-a/bc-/akl”，但我只得到“abcakl”。请帮忙。谢谢。

Answer 1

您需要将算子逻辑放在主循环中。

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int Prec(char c)
{
    if(c == '^')
    {
        return 3;
    }

    else if(c == '*' || c == '/')
    {
        return 2;
    }

    else if(c == '+' || c == '-')
    {
        return 1;
    }

    else
    {
        return -1;
    }
} // prec

string InfixToPrefix(string s)
{
    reverse(s.begin(), s.end());

    stack<char> st;
    string res;

    for(int i=0; i<s.length(); i++)
    {
        if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
        {
            res += s[i];
        }

        else if(s[i] == ')')
        {
            st.push(s[i]);
        }

        else if(s[i] == '(')
        {
            while(!st.empty() && st.top() != ')')
            {
                res += st.top();
                st.pop();
            }

            if(!st.empty())
            {
                st.pop();
            }

            else
            {
                while(!st.empty() && Prec(st.top()) >= Prec(s[i]))
                {
                    res += st.top();
                    st.pop();
                }

                st.push(s[i]);
            }
        }
        else {   // added operator logic to the main portion of the parse loop
            if (!st.empty() && Prec(st.top()) >= Prec(s[i])){
                    res += st.top();
                    st.pop();
            }

                st.push(s[i]);
        }
    } // for loop

    while(!st.empty())
    {
        res+=st.top();
        st.pop();
    }

    reverse(res.begin(), res.end());

    return res;
} // InfixToPrefix()

int main()
{
    cout<<InfixToPrefix("(a-b/c)*(a/k-l)")<<endl;
}

Stack Infix to Prefix 无法正常工作

Stack Infix to Prefix not working correctly

c++

stack