Click here to Skip to main content
15,042,397 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Hi,

I am writing A Post Fix Calculator program, but having trouble identifying the loop invariant. I have tried looking for examples on the internet and on Youtube but most of the examples are for easy functions that usually do not involve a lot of if-statements.

The algorithm pushes some number taken from the user into the stack and then pops the last two numbers in the stack if the user enters an arithmic operator and pushes the result back into the stack.

I really appreciated any hints on what the loop invariant should be for this algorithm. Also, any resources you know (internet, books, ebooks) that provide an explanation for the loop invariant as well as examples for more complicated algorithms that involve if-statements and taking input from user is appreciated!


Java
public static void main(String [] args){
		
		Scanner keyboard = new Scanner(System.in);//to read input from the user
		Stack stack = new Stack();                //to push user input into the stack if it is a number
		String input = "";                        //to save user input into a variable
		int tempVar = 0;                          //to save a poped number for calculation
		
		System.out.println("\nWelcome To The Postfix Calculator!");//printing message for the user
		
		do{
			//ask user to enter a value
			System.out.print("\nEnter a number or an arthmetic operator, or 0 to display the result: ");
			
			input = keyboard.nextLine(); //put user input into a variable
			
			/*If input is "+" the last two elements in the stack are poped and their addition 
			 * is pushed into the stack*/
			if(input.equals("+")){
				tempVar = (int)stack.pop();
				tempVar = (int)stack.pop() + tempVar;
				stack.push(tempVar);
			}
			
			/*If input is "-" the last two elements in the stack are poped and their subctraction 
			 * is pushed into the stack*/
			else if(input.equals("-")){
				tempVar = (int)stack.pop();
				tempVar = (int)stack.pop() - tempVar;
				stack.push(tempVar);
			}
			
			/*If input is "*" the last two elements in the stack are poped and their multiplication 
			 * is pushed into the stack*/
			else if(input.equals("*")){
				tempVar = (int)stack.pop();
				tempVar = (int)stack.pop() * tempVar;
				stack.push(tempVar);
			}
			
			/*If input is "/" the last two elements in the stack are poped and their division 
			 * is pushed into the stack*/
			else if(input.equals("/")){
				tempVar = (int)stack.pop();
				tempVar = (int)stack.pop() / tempVar;
				stack.push(tempVar);
			}
			
			/*If input is none of these and not "0" then the number is parsed and pushed into the
			 * stack*/
			else if(!input.equals("0"))
				stack.push(Integer.parseInt(input));
			
		}
		while(!input.equals("0"));
		
		if(stack.empty())
			System.out.println("\nYou haven't entered any value, please try again.");
		else
			System.out.println("\nFinal Value: " +  stack.pop());
		
	}


What I have tried:

I have tried looking into some examples on the loop invariant, but couldn't find examples for more complicated algorithms
Posted
Updated 18-Jun-16 10:16am
v2
Comments
Sergey Alexandrovich Kryukov 18-Jun-16 17:59pm
   
Why would you need such examples? Do you understand what does it mean, loop invariant? If you do, you can build the invariant you need. I don't see how "easy" samples are different from "complicated" ones and why they are important.

Maybe your whole approach is wrong, or rather artificial. Do you think that an invariant is something you have to find? No, it comes from the algorithm. Probably, your mistake is the notion "invariant should be for this algorithm". No, nothing "should". Invariant is just one of the mathematical and algorithmic techniques which may or may not be useful. I have no idea what makes you thinking that it "should be" there, in this particular case.

In other words, your purpose and motivation are totally unclear.

—SA
Member 12569032 18-Jun-16 19:05pm
   
My purpose is finding all loop invariant necessary to formally prove that the algorithm does what it is created for using induction. User input is assumed to be correct and I need to prove partial correction only (proving termination is not needed).
   
Invariant is not the only device for the proof and not always applicable...
—SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900