中缀到postfix转换器

我一直在使用这个中缀到postfix / polis表示法转换器。 虽然，我觉得解决方案不够充分。 特别是j（编辑：现在称为索引）变量正在困扰我。

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

public static string[] InfixToPostfix(string[] infixArray) { var stack = new Stack(); var postfix = new string[infixArray.Length]; int index = 0; string st; for (int i = 0; i  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

如果用Stack替换array ，则不必跟踪index变量的位置。

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

我的实施：

 public static string[] InfixToPostfix( string[] infixArray ) { var stack = new Stack(); var postfix = new Stack(); 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

这是维基百科有关infix，postfix和Shunting Yard算法的信息的一个非常基本的实现（数字，括号和+ – / *运算符）。 可以整理和改进，我将为我自己的工作做，但我在这里发布之前我自定义它无法识别：

 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 InfixTokens { get; set; } public Stack PostfixTokens { get; set; } public string RawFormula { get; set; } public Formula(string rawFormula) { // store the raw formula RawFormula = rawFormula; InfixTokens = new Stack(); PostfixTokens = new Stack(); #region generate the InFix Stack Stack tokens = new Stack(); 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 reversedStack = new Stack(); 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 infixTokens = new Stack(InfixTokens); Stack InFixStack = new Stack(); while (infixTokens.Count > 0) InFixStack.Push(infixTokens.Pop()); // new stacks Stack output = new Stack(); Stack operators = new Stack(); 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(); while (output.Count > 0) reversedStack.Push(output.Pop()); // store in the Tokens property PostfixTokens = reversedStack; #endregion } public decimal Calculate() { Stack EvaluationStack = new Stack(); // get a reversed copy of the tokens Stack postFixStack = new Stack(PostfixTokens); Stack PostFixStack = new Stack(); 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