Infix to postfix converter
I am working on this infix for Postfix / Polis notification converter. Although, I don't think the solution is adequate. In particular, the variable j (EDIT: Now called index) is eavesdropping on me.
Do you have any suggestions? Or maybe there is a much better way to do this? Or am I just too worried?
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();
}
+2
source to share
4 answers
If you replace array
with Stack<string>
, you don't need to keep track of where you are with the variable index
.
Then you can return the result with postfixStack.ToArray()
My implementation:
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();
}
+4
source to share
Here is a very simple implementation (numbers, parentheses, and only + - / * operators) of wikipedia information about infixes, postfixes, and the Shunting Yard algorithm. Could be neat and improved on what I will do for my own work, but I am posting here before tweaking it beyond recognition:
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 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 a bracket
else if (currentToken.GetType() == typeof(Parenthesis))
{
switch (((Parenthesis)currentToken).ParenthesisType)
{
// if it an opening bracket, add it to operators
case ParenthesisTypes.Open:
operators.Push(currentToken);
break;
// if it 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 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();
}
}
}
+3
source to share
Try it. It took me a while to code this, but it works for all the examples I found on the internet.
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);
}
0
source to share
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();
}
}
}
0
source to share