infix zu postfix-Wandler
https://stackoverflow.com/questions/1438030
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe auf dieser infix zu postfix / polis Notation Konverter arbeitet. Obwohl, fühle ich mich nicht die Lösung ausreichend ist. Insbesondere die j (EDIT: Nun genannt Index). Variable mich nervt
Haben Sie Jungs irgendwelche Vorschläge? Oder vielleicht gibt es eine viel bessere Weise, sie zu erreichen? Oder habe ich einfach zu viel Sorgen machen?
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();
}
Lösung
Wenn Sie array durch eine Stack<string> ersetzen, müssen Sie nicht den Überblick behalten, wo Sie mit dem index variabel sind.
Sie können dann wieder Ihr Ergebnis mit postfixStack.ToArray()
Meine Implementierung:
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();
}
Andere Tipps
Dies ist eine sehr einfache Implementierung (Zahlen, Klammern und + - / * Anbieter) der Informationen auf Wikipedia über Infix, Postfix & Rangierbahnhof Algorithmus. Könnte neatened up & verbessert auf, die ich für meine eigene Arbeit tun werde, aber ich bin Entsendung hier, bevor ich es bis zur Unkenntlichkeit anpassen:
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();
}
}
}
Versuchen Sie dies. Es dauert eine Weile, dies zu kodieren, sondern arbeitet für alle Beispiele, die ich im Internet gefunden.
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);
}
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();
}
}
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
