[Vermiculus]

This algorithm came to me a couple days ago, but I have a very limited knowledge of the C++ string class and pointers (should probably read up on those pointers). Can anybody donate some code to do this? I have tried unsuccessfully; there is a limit to how much you can rely on for(;; ) loops.

The images is animated and text-based. I find it is much easier to explain the algorithm if it is animated thus, but I will be posting a textual format soon - just have to work out the wording. The GIF file is 83.6 KB. Yes, KB, but I in fact know people who would find that to be a rather large download size, although at second thought they probably wouldn't be on this site then.... Oh well. At least we get to see the new tags!



I was thinking converting it to a C-style string and then using pointers, but could a string::iterator be used here as well? Again, just throwing out ideas. I would really love to see this parser get out there.

edit: spoiler tag broken

This post has been edited by NickDMax: 20 March 2010 - 07:28 AM

[KYA]

What?


You want help writing a string parsing function? Something else?


Ideally, you'd have an Operator enum/class and check each index, pushing onto an operator/operand stack depending on how you're parsing (pre/post/infix for example).

[Vermiculus]

KYA, on 19 March 2010 - 09:25 PM, said:

Ideally, you'd have an Operator enum/class and check each index, pushing onto an operator/operand stack depending on how you're parsing (pre/post/infix for example).

Could you elaborate? I'm still relatively new to C++ - only came to a rudimentary understanding of OOP a few months ago. How would this Operator class work, and how would I be able to identify it in a larger function such as "45+2+48-48+12+48+65+4845-59+0.51-87.158" or a variable function such as "8*x*x-4*x+8"?

[KYA]

The only example code I have on hand is some Java I wrote for a class a while back. This example wouldn't handle variables, but I'm sure you could add it. Enums don't act the same in C++, but the concept is similar:

//enum for Operator "objects" 
 import java.util.*;
 
public enum Operator {
	
	ADD("+", 1)
	{
		double doCalc(double d1, double d2) {
			return d1+d2;
		}
	},
	SUBTRACT("-",1)
	{
		double doCalc(double d1, double d2) {
			return d1-d2;
		}
	},
	MULTIPLY("*", 2)
	{
		double doCalc(double d1, double d2) {
			return d1*d2;
		}
	},
	DIVIDE("/",2)
	{
		double doCalc(double d1, double d2) {
			return d1/d2;
		}
	},
	STARTBRACE("(", 0)
	{
		double doCalc(double d1, double d2) {
			return 0;
		}
	},
	ENDBRACE(")",0)
	{
		double doCalc(double d1, double d2) {
			return 0;
		}
	},
	EXP("^", 3)
	{
		double doCalc(double d1, double d2) {
			return Math.pow(d1,d2);
		}
	};
	
	private String operator;
	private int precedence;
	
	private Operator(String operator, int precedence) {
		this.operator = operator;
		this.precedence = precedence;
	}
	
	public int getPrecedenceLevel() {
		return precedence;
	}
	
	public String getSymbol() {
		return operator;
	}
	
	public static boolean isOperator(String s) {
		for(Operator op : Operator.values()) { //iterate through enum values
			if (op.getSymbol().equals(s))
				return true;
		}
		return false;
	}
	
	public static Operator getOperator(String s) 
		throws InvalidOperatorException {
			for(Operator op : Operator.values()) { //iterate through enum values
				if (op.getSymbol().equals(s))
					return op;
			}
			throw new InvalidOperatorException(s + " Is not a valid operator!");
	}
	
	public boolean isStartBrace() {
		return (operator.equals("("));
	}
	//overriding calculation provided by each enum part
	abstract double doCalc(double d1, double d2);
}
//error to be thrown/caught in ProjectOne.java
class InvalidOperatorException extends Exception {
    public InvalidOperatorException() {
    }

    public InvalidOperatorException(String s) {
        super(s);
    }
}



//reading in a string at doing the parsing/arithmetic 
public static void main (String[] args) {
	 String input = "";
	 //get input
	 System.out.print("Enter an infix expression: ");
        BufferedReader in = new BufferedReader(
                                new InputStreamReader(System.in));
        try {                        
        	input = in.readLine();
        }
        catch (IOException e)
        {
        	System.out.println("Error getting input!");
        }
        	
        doCalculate(input);
 	}
 	
 	// Input: user entered string
 	// Output: Display of answer
 	public static void doCalculate(String equation) {
 		//our stacks for storage/temp variables
	 	Stack<Operator> operatorStack;
	 	Stack<Double> operandStack;
	 	double valOne, valTwo, newVal;
	 	Operator temp;
	 	
	 	//initalize
 		StringTokenizer tokenizer = new StringTokenizer(equation, " +-*/()^", true);
 		String token = "";
 		operandStack = new Stack();
 		operatorStack = new Stack();
	 	try {
		 		while(tokenizer.hasMoreTokens()){ //run through the string
		 			token = tokenizer.nextToken();
		 			if (token.equals(" ")) { //handles spaces, goes back up top
		 				continue;
		 			}
		            else if (!Operator.isOperator(token)){ //number check
		            	operandStack.push(Double.parseDouble(token));
		            }
		            else if (token.equals("(")) {
		            	operatorStack.push(Operator.getOperator(token));
		            }
		            else if (token.equals(")")) { //process until matching paraentheses is found
		            	while (!((temp = operatorStack.pop()).isStartBrace())) {
		            		valTwo = operandStack.pop();
		            		valOne = operandStack.pop();
		            		newVal = temp.doCalc(valOne, valTwo);
		            		operandStack.push(newVal);
		            	}
		            }
		            else { //other operators
		            	while (true) { //infinite loop, check for stack empty/top of stack '('/op precedence
		            		if ((operatorStack.empty()) || (operatorStack.peek().isStartBrace()) || 
		            			(operatorStack.peek().getPrecedenceLevel() < Operator.getOperator(token).getPrecedenceLevel())) {
		            				operatorStack.push(Operator.getOperator(token));
		            			    break; //exit inner loop
		            		}
			            	temp = operatorStack.pop();
			            	valTwo = operandStack.pop();
			            	valOne = operandStack.pop();
			            	//calculate and push
			            	newVal = temp.doCalc(valOne, valTwo);
			            	operandStack.push(newVal);
		            	}
		            }
		 		}
	 		}
	 		catch (InvalidOperatorException e) {
	 			System.out.println("Invalid operator found!");
	 		}
	 		
	 		//calculate any remaining items (ex. equations with no outer paraentheses)
	 		while(!operatorStack.isEmpty()) {
		 		temp = operatorStack.pop();
	        	valTwo = operandStack.pop();
	        	valOne = operandStack.pop();
	        	newVal = temp.doCalc(valOne, valTwo);
	        	operandStack.push(newVal);
	 		}
        	//print final answer
	 		System.out.println("Answer is: " + operandStack.pop()); 
 		}

I haven't looked/revised this in months, so I'm sure there's some optimization that could be done.

[Vermiculus]

Is a Java 'stack' similar to the C++ vector?
And what exactly is a Token? I've seen this term used alot, but I still have only a vague understanding of what it is... the MSDN Documentation isn't very specific about it, but I'm sure it's one of those tools in C++ that's found everywhere commercially. How do you create and use tokens?

{ quick google search ensuing }

[Vermiculus]

I've found some code:

int main ()
{
  char str[] ="- This, a sample string.";
  char * pch;
  printf ("Splitting string \"%s\" into tokens:\n",str);
  pch = strtok (str," ,.-");
  while (pch != NULL)
  {
    printf ("%s\n",pch);
    pch = strtok (NULL, " ,.-");
  }
  return 0;
}

It seems that all tokens really do is split a string into terms, but how could longer "tokens" be used, such as 'log' or 'sin'? And what exactly is the output of the function? Does it output the array of tokens, or just the next token in line?

[Vermiculus]

I have no idea what that means But I have made considerable headway on my problem.

The only problem I'm having right now is with my Parenthetical parser. For some reason, the final Param turns out to be nasty.

   printf("\nEntered Parenthesis Parser");
   string Param;
   for(unsigned int index = 0; index < this->definition.length(); index++)
   {
      if(this->definition[index] == '(')
      {
         for(unsigned int index2 = index + 1; index2 < this->definition.length(); index2++)
         {
            if(this->definition[index2] == ')')
               break;
            Param.append(&this->definition[index2]);
         }
         std::cout << Param.c_str();
         Function theParam(Param, this->parameter);
         std::cout << theParam.Evaluate(this->argument);
      }
   }

Let's say I enter "1x(2x)3x" for f(x). My Implied Multiplication Parser (which works like a bowl of lucky charms) parses the string to mean "1*x*(2*x)*3*x". When the ParentheticalParser is invoked however, the parameter it sends to be evaluated is "2*x)*3*x*x)*3*xx)*3*x".
I have absolutely no idea what is going on; presumably the error has something to do with the for loop, but I am unsure.

This post has been edited by Vermiculus: 20 March 2010 - 04:33 PM