中缀到后缀转换器

Question

我一直在研究这个中缀到后缀/polis 符号转换器。 尽管如此，我认为这个解决方案还不够。 特别是 j （编辑：现在称为索引）变量困扰着我。

你们有什么建议吗？或者也许有更好的方法来实现它？还是我担心太多了？

public static string[] InfixToPostfix(string[] infixArray)
{
    var stack = new Stack<string>();
    var postfix = new string[infixArray.Length];

    int index = 0;
    string st;
    for (int i = 0; i < infixArray.Length; i++)
    {
        if (!(MyMath.MathOperators.Contains(infixArray[i])))
        {
            postfix[index] = infixArray[i];
            index++;
        }
        else
        {
            if (infixArray[i].Equals("("))
            {
                stack.Push("(");
            }
            else if (infixArray[i].Equals(")"))
            {
                st = stack.Pop();
                while (!(st.Equals("(")))
                {
                    postfix[index] = st;
                    index++;
                    st = stack.Pop();
                }
            }
            else
            {
                while (stack.Count > 0)
                {
                    st = stack.Pop();
                    if (RegnePrioritet(st) >= RegnePrioritet(infixArray[i]))
                    {
                        postfix[index] = st;
                        index++;
                    }
                    else
                    {
                        stack.Push(st);
                        break;
                    }
                }
                stack.Push(infixArray[i]);
            }
        }
    }
    while (stack.Count > 0)
    {
        postfix[index] = stack.Pop();
        index++;
    }

    return postfix.TakeWhile(item => item != null).ToArray();
}

Answer 1

如果将 array 替换为 Stack，则无需使用 index 变量来跟踪当前位置。

然后，您可以使用 postfixStack.ToArray() 返回结果

我的实现：

public static string[] InfixToPostfix( string[] infixArray )
{
    var stack = new Stack<string>();
    var postfix = new Stack<string>();

    string st;
    for ( int i = 0 ; i < infixArray.Length ; i++ )
    {
        if ( !( "()*/+-".Contains( infixArray[ i ] ) ) )
        {
            postfix.Push(infixArray[i]);
        }
        else
        {
            if ( infixArray[ i ].Equals( "(" ) )
            {
                stack.Push( "(" );
            }
            else if ( infixArray[ i ].Equals( ")" ) )
            {
                st = stack.Pop();
                while ( !( st.Equals( "(" ) ) )
                {
                    postfix.Push( st );
                    st = stack.Pop();
                }
            }
            else
            {
                while ( stack.Count > 0 )
                {
                    st = stack.Pop();
                    if ( RegnePrioritet( st ) >= RegnePrioritet( infixArray[ i ] ) )
                    {
                        postfix.Push(st);
                    }
                    else
                    {
                        stack.Push( st );
                        break;
                    }
                }
                stack.Push( infixArray[ i ] );
            }
        }
    }
    while ( stack.Count > 0 )
    {
        postfix.Push(stack.Pop());
    }

    return postfix.Reverse().ToArray();
}

Answer 2

这是维基百科上有关中缀、后缀和后缀信息的非常基本的实现（仅数字、括号和 +-/* 运算符）。调车场算法。可以整理一下&改进了，我会为自己的工作做这件事，但在我将其定制得面目全非之前，我先在这里发布：

using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;

namespace Infix_to_Postfix
{
    #region enums
    enum TokenTypes
    {
        Operator,
        Number,
        Parenthesis
    }
    enum Associativenesses
    {
        Left,
        Right
    }
    enum OperatorTypes { Plus, Minus, Multiply, Divide, Equals, Exclamation, Modulus }
    enum ParenthesisTypes { Open, Close }
    #endregion

    #region classes
    public class Token { }

    class Operator : Token
    {
        public OperatorTypes OperatorType { get; set; }
        public Operator(OperatorTypes operatorType) { OperatorType = operatorType; }
        public int Precedence
        {
    get
    {
        switch (this.OperatorType)
        {
            case OperatorTypes.Exclamation:
        return 4;
            case OperatorTypes.Multiply:
            case OperatorTypes.Divide:
            case OperatorTypes.Modulus:
        return 3;
            case OperatorTypes.Plus:
            case OperatorTypes.Minus:
        return 2;
            case OperatorTypes.Equals:
        return 1;
            default:
        throw new Exception("Invalid Operator Type for Precedence get");
        }
    }
        }
        public Associativenesses Associativeness
        {
    get
    {
        switch (this.OperatorType)
        {
            case OperatorTypes.Equals:
            case OperatorTypes.Exclamation:
        return Associativenesses.Right;
            case OperatorTypes.Plus:
            case OperatorTypes.Minus:
            case OperatorTypes.Multiply:
            case OperatorTypes.Divide:
            case OperatorTypes.Modulus:
        return Associativenesses.Left;
            default:
        throw new Exception("Invalid Operator Type for Associativeness get");
        }
    }
        }
        public override string ToString()
        {
    switch (OperatorType)
    {
        case OperatorTypes.Plus: return "+";
        case OperatorTypes.Minus: return "-";
        case OperatorTypes.Multiply: return "*";
        case OperatorTypes.Divide: return "/";
        case OperatorTypes.Equals: return "=";
        case OperatorTypes.Exclamation: return "!";
        case OperatorTypes.Modulus: return "%";
        default: return null;
    }
        }
        public static OperatorTypes? GetOperatorType(string operatorValue)
        {
    switch (operatorValue)
    {
        case "+": return OperatorTypes.Plus;
        case "-": return OperatorTypes.Minus;
        case "*": return OperatorTypes.Multiply;
        case "/": return OperatorTypes.Divide;
        case "=": return OperatorTypes.Equals;
        case "!": return OperatorTypes.Exclamation;
        case "%": return OperatorTypes.Modulus;
        default: return null;
    }
        }
    }

    class Parenthesis : Token
    {
        public ParenthesisTypes ParenthesisType { get; set; }
        public Parenthesis(ParenthesisTypes parenthesisType) { ParenthesisType = parenthesisType; }
        public override string ToString() { if (ParenthesisType == ParenthesisTypes.Open) return "("; else return ")"; }
        public static ParenthesisTypes? GetParenthesisType(string parenthesisValue)
        {
    switch (parenthesisValue)
    {
        case "(": return ParenthesisTypes.Open;
        case ")": return ParenthesisTypes.Close;
        default: return null;
    }
        }
    }

    class Numeric : Token
    {
        public decimal Value { get; set; }
        public Numeric(decimal value) { Value = value; }
        public override string ToString() { return Value.ToString(); }
    }

    public class Formula
    {
        public Stack<Token> InfixTokens { get; set; }
        public Stack<Token> PostfixTokens { get; set; }
        public string RawFormula { get; set; }

        public Formula(string rawFormula)
        {
    // store the raw formula
    RawFormula = rawFormula;
    InfixTokens = new Stack<Token>();
    PostfixTokens = new Stack<Token>();

    #region generate the InFix Stack
    Stack<Token> tokens = new Stack<Token>();
    string store = "";

    // parse the formula into a stack of tokens
    while (rawFormula.Length > 0)
    {
        string ThisChar = rawFormula.Substring(0, 1);

        if (Regex.IsMatch(ThisChar, "[0-9\\.]"))
        {
            // a numeric char, so store it until the number is reached
            store += ThisChar;

        }
        else if (Operator.GetOperatorType(ThisChar) != null)
        {
            // a value is stored, so add it to the stack before processing the operator
            if (store != "")
            {
        tokens.Push(new Numeric(Convert.ToDecimal(store)));
        store = "";
            }
            tokens.Push(new Operator((OperatorTypes)Operator.GetOperatorType(ThisChar)));
        }
        else if (Parenthesis.GetParenthesisType(ThisChar)!=null)
        {
            // a value is stored, so add it to the stack before processing the parenthesis
            if (store != "")
            {
        tokens.Push(new Numeric(Convert.ToDecimal(store)));
        store = "";
            }
            tokens.Push(new Parenthesis((ParenthesisTypes)Parenthesis.GetParenthesisType(ThisChar)));
        }
        else
        {
            // ignore blanks (unless between to numbers)
            if (!(ThisChar == " " && !(store != "" && Regex.IsMatch(rawFormula.Substring(1, 1), "[0-9\\.]"))))
            {
        throw new Exception("Invalid character in Formula: " + ThisChar);
            }
        }
        // move to the next position
        rawFormula = rawFormula.Substring(1);
    }

    // if there is still something in the numeric store, add it to the stack
    if (store != "")
    {
        tokens.Push(new Numeric(Convert.ToDecimal(store)));
    }

    // reverse the stack
    Stack<Token> reversedStack = new Stack<Token>();
    while (tokens.Count > 0) reversedStack.Push(tokens.Pop());

    // store in the Tokens property
    InfixTokens = reversedStack;
    #endregion

    #region generate the PostFix Stack
    // get a reversed copy of the tokens
    Stack<Token> infixTokens = new Stack<Token>(InfixTokens);
    Stack<Token> InFixStack = new Stack<Token>();
    while (infixTokens.Count > 0) InFixStack.Push(infixTokens.Pop());
    // new stacks
    Stack<Token> output = new Stack<Token>();
    Stack<Token> operators = new Stack<Token>();

    while (InFixStack.Count > 0)
    {
        Token currentToken = InFixStack.Pop();

        // if it's an operator
        if (currentToken.GetType() == typeof(Operator))
        {
            // move precedent operators to output
            while (operators.Count > 0 && operators.Peek().GetType() == typeof(Operator))
            {
        Operator currentOperator = (Operator)currentToken;
        Operator nextOperator = (Operator)operators.Peek();
        if ((currentOperator.Associativeness == Associativenesses.Left && currentOperator.Precedence <= nextOperator.Precedence)
            || (currentOperator.Associativeness == Associativenesses.Right && currentOperator.Precedence < nextOperator.Precedence))
        {
            output.Push(operators.Pop());
        }
        else
        {
            break;
        }
            }
            // add to operators
            operators.Push(currentToken);
        }
        // if it's a bracket
        else if (currentToken.GetType() == typeof(Parenthesis))
        {
            switch (((Parenthesis)currentToken).ParenthesisType)
            {
        // if it's an opening bracket, add it to operators
        case ParenthesisTypes.Open:
            operators.Push(currentToken);
            break;
        // if it's a closing bracket
        case ParenthesisTypes.Close:
            // shift operators in between opening to output 
            while (operators.Count > 0)
            {
                Token nextOperator = operators.Peek();
                if (nextOperator.GetType() == typeof(Parenthesis) && ((Parenthesis)nextOperator).ParenthesisType == ParenthesisTypes.Open) break;
                output.Push(operators.Pop());
            }
            // add to operators
            operators.Pop();
            break;
            }
        }
        // if it's numeric, add to output
        else if (currentToken.GetType() == typeof(Numeric))
        {
            output.Push(currentToken);
        }

    }

    // for all remaining operators, move to output
    while (operators.Count > 0)
    {
        output.Push(operators.Pop());
    }

    // reverse the stack
    reversedStack = new Stack<Token>();
    while (output.Count > 0) reversedStack.Push(output.Pop());

    // store in the Tokens property
    PostfixTokens = reversedStack;
    #endregion
        }

        public decimal Calculate()
        {
    Stack<Numeric> EvaluationStack = new Stack<Numeric>();
    // get a reversed copy of the tokens
    Stack<Token> postFixStack = new Stack<Token>(PostfixTokens);
    Stack<Token> PostFixStack = new Stack<Token>();
    while (postFixStack.Count > 0) PostFixStack.Push(postFixStack.Pop());

    while (PostFixStack.Count > 0)
    {
        Token currentToken = PostFixStack.Pop();

        if (currentToken.GetType() == typeof(Numeric))
        {
            EvaluationStack.Push((Numeric)currentToken);
        }
        else if (currentToken.GetType() == typeof(Operator))
        {
            Operator currentOperator = (Operator)currentToken;
            if (currentOperator.OperatorType == OperatorTypes.Plus
        || currentOperator.OperatorType == OperatorTypes.Minus
        || currentOperator.OperatorType == OperatorTypes.Multiply
        || currentOperator.OperatorType == OperatorTypes.Divide)
            {
        decimal FirstValue = EvaluationStack.Pop().Value;
        decimal SecondValue = EvaluationStack.Pop().Value;
        decimal Result;

        if (currentOperator.OperatorType == OperatorTypes.Plus)
        {
            Result = SecondValue + FirstValue;
        }
        else if (currentOperator.OperatorType == OperatorTypes.Minus)
        {
            Result = SecondValue - FirstValue;
        }
        else if (currentOperator.OperatorType == OperatorTypes.Divide)
        {
            Result = SecondValue / FirstValue;
        }
        else if (currentOperator.OperatorType == OperatorTypes.Multiply)
        {
            Result = SecondValue * FirstValue;
        }
        else
        {
            throw new Exception("Unhandled operator in Formula.Calculate()");
        }
        EvaluationStack.Push(new Numeric(Result));
        Console.WriteLine("EVAL: " + SecondValue.ToString() + " " + currentOperator.ToString() + " " + FirstValue.ToString() + " = " + Result.ToString());
            }
        }
        else
        {
            throw new Exception("Unexpected Token type in Formula.Calculate");
        }
    }

    if (EvaluationStack.Count != 1)
    {
        throw new Exception("Unexpected number of Tokens in Formula.Calculate");
    }
    return EvaluationStack.Peek().Value;
        }
    }
    #endregion

    class Program
    {
        static void Main(string[] args)
        {
    try
    {
        string Equation = "";
        Equation = "1+2+3";
        Equation = "(((12.7+2)/3)-10)*(32+(3*5))";
        Equation = "5 + ((1 + 2) * 4) - 3";
        Equation = "1 + (3 * 4) - 3";
        Equation = "5+8-(2*2)";
        Equation = "10/2+3/2*4-2+4*3/4-9";
        Equation = "6/2*4";
        Equation = "3 + 4 * 2 / ( 1 - 5 ) ";
        Console.WriteLine("EQUATION: " + Equation);

        Formula formula = new Formula(Equation);
        Console.WriteLine("INFIX: " + String.Join(" ", formula.InfixTokens));
        Console.WriteLine("POSTFIX: " + String.Join(" ", formula.PostfixTokens));

        decimal Result = formula.Calculate();
        Console.WriteLine("RESULT: " + Result.ToString());
    }
    catch (Exception Err)
    {
        Console.WriteLine("ERROR: " + Err.Message);
    }

    Console.ReadLine();
        }
    }
}

Answer 3

试试这个。我花了一段时间来编写此代码，但适用于我在互联网上找到的每个示例。

public void evaluate(Stack stk){
    Stack output= new Stack();
    Stack operators= new Stack();
    while(!stk.isEmpty()){
        String str = stk.get(0).toString();
        str = str.replace("\\s", "");
        stk.removeElementAt(0);
        if(isNumerical(str)){
            output.push(str);
        }

        else if(!isNumerical(str)){


        char c = str.charAt(0);
        System.out.println(c);


            if(c=='('){
                operators.push(c);



            }
            else if(c==')'){

                char x= operators.pop().toString().charAt(0);

                while(x!='('){
                    System.out.println("That line excecuted and removed the char "+x);
                    output.push(x);
                    x=operators.pop().toString().charAt(0);

                }

            }
            else if(!output.isEmpty() && !operators.isEmpty()){

                System.out.println("Printme");
                  char s= operators.lastElement().toString().charAt(0);
                   System.out.println(s);
                   System.out.println(c);
                   if(precedenceNum(s)>=precedenceNum(c)){

                    String op =operators.pop().toString();
                    output.push(op);
                    operators.push(str);
                   }
                   else{
                    operators.push(str);
                }


               }
            else if(operators.isEmpty()){
                operators.push(str);
            }


                System.out.println(operators);

            }

        }
    while(!operators.isEmpty()){
        output.push(operators.pop());
    }



    System.out.println(output);




}

Answer 4

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace infix_to_postfix
{
    class Program
    {
        static void Main(string[] args)
        {

            int i = new int();
            Console.WriteLine("Enter the length of notation:");

            //bool extra = new bool();
            //do {
            //    try
            //    {
                    i = Convert.ToInt32(Console.ReadLine());     //enter the length of notation
                //}
                //catch
                //{
                    //Console.WriteLine("Please Get Out");
            //        extra = false;

            //    }
            //} while (extra== false);


            string[] infix = new string[i];
            string[] postfix = new string[i];
            string[] temp = new string[i];



            Console.WriteLine("Enter values");
            int l = 0;
            for ( l = 0; l < i; l++) 
            {

                infix[l] = Console.ReadLine();
            }



            int x = 0;
            Console.Write("Infix:");
            for ( x = 0; x < i; x++) 
            {

                Console.Write( infix[x]);
            }



            //      removing paranthesis
            for(int z=i-1;z>=0;z--)
            {

                int c = z;
                if (infix[z] == "(")
                {
                    infix[z] = null;
                }
                if (infix[z] == "+" || infix[z] == "*" || infix[z] == "/" || infix[z] == "-")
                {
                    do
                    {
                        c++;
                        if (infix[c] == ")")
                        {
                            infix[c] = infix[z];
                            infix[z] = null;
                            break;
                        }
                    }
                    while (c < i) ;


                }

            }

            //filling up

            int lagao = 0;

            for(int v=0;v<i;v++)
            {
                if(infix[v]!=null )
                {
                    postfix[lagao] = infix[v];
                    lagao++;
                }
            }


            int p = 0;
            Console.Write("postfix:");
            for (p = 0; p < i; p++)
            {

                Console.Write(postfix[p]);
            }






            //int s = new int();
            //switch(s)
            //{
            //    case 1:
            //        break;
            //    case 2:
            //        break;
            //    case 3:
            //        break;
            //    default:
            //        break;
            //}


            Console.ReadKey();
        }

    }
}