접미사 - 접미사 변환기

나는이 접미사를 접미사/폴리스 표기법 변환기로 작업하고 있습니다. 비록 솔루션이 적절하다고 생각하지 않습니다. 특히 j (EDIT : 인덱스라고 함) 변수가 나를 괴롭 히고 있습니다.접미사 - 접미사 변환기

의견이 있으십니까? 아니면 그것을 수행하는 훨씬 더 좋은 방법이 있을까요? 또는 나는 다만 너무 많이 고민해? 당신이 Stack<string>에 의해 array를 교체 할 경우

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(); 
}

출처

2009-09-17 CasperT

없음 시간은 지금이 탐구하는,하지만 당신은이에 대한 [전철 야드 알고리즘을 (http://en.wikipedia.org/wiki/Shunting_yard_algorithm) 구현되어야합니다. 정확히 당신이 가진 것일 수도 있지만, 어쨌든 그것을 추가 할 것만 같았습니다. – Noldorin

지옥은 RegnePrioritet 무엇입니까? 그리고 그것은 무엇을합니까? –

, 당신은 당신이 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(); 
}

출처

2009-09-17 11:05:31

흠, 스택에 잘못된 순서로 된 것이 없습니까? – CasperT

잘 모르겠습니다. 알고리즘에 대해 깊이 파고 들지 않았습니다. 그렇다면 ToArray를 호출하기 전에 '역방향'을 호출 할 수 있습니다. –

구현을 보여 주시겠습니까? 나는 너를 upvote하고 대답을 받아 들인다 :) – CasperT

이 (번호, 괄호 + - 만/* 사업자) 아주 기본적인 구현에 대한 위키 백과 정보 중위, 후위 & Shunting Yard 알고리즘. 최대 neatened 될 수 있습니다 & 내가 내 자신의 일을 다하겠습니다하는에 개선,하지만 인식을 넘어 그것을 사용자 정의하기 전에 내가 여기에 게시하도록하겠습니다 :

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(); 
     } 
    } 
}

출처

2011-10-14 15:02:51 Sean

이보십시오. 이 코드를 작성하는 데는 시간이 걸리지 만 인터넷에서 찾은 모든 예제에서 작동합니다.

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); 




}

출처

2015-01-28 14:28:34

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(); 
     } 

    } 
}

출처

2017-10-11 18:51:25

접미사 - 접미사 변환기

답변

관련 문제