Posted on by Kalkicode
Code Stack

Infix to prefix conversion using stack in ruby

Ruby program for Infix to prefix conversion using stack. Here problem description and other solutions.

#  Ruby program for
#  Infix to prefix conversion

#  Stack node
class StackNode 
	# Define the accessor and reader of class StackNode
	attr_reader :element, :next
	attr_accessor :element, :next
	#  Stack data
	def initialize(element, other) 
		self.element = element
		self.next = other
	end

end

#  Define a custom stack
class MyStack 
	# Define the accessor and reader of class MyStack
	attr_reader :top, :size
	attr_accessor :top, :size
	def initialize() 
		self.top = nil
		self.size = 0
	end

	#  Add node at the top of stack
	def push(element) 
		self.top = StackNode.new(element, self.top)
		self.size += 1
	end

	def isEmpty() 
		if (self.size > 0 && self.top != nil) 
			return false
		else
 
			return true
		end

	end

	#  Remove top element of stack
	def pop() 
		c = ""
		if (self.size > 0 && self.top != nil) 
			temp = self.top
			#  Change top element of stack
			self.top = temp.next
			self.size -= 1
			c = temp.element
		end

		return c
	end

	#  Return top element of stack
	def peek() 
		if (self.top == nil) 
			return ""
		end

		return self.top.element
	end

end

class Conversion 
	def precedence(text) 
		if (text == "+" || text == "-") 
			return 1
		elsif(text == "*" || text == "/") 
			return 2
		elsif(text == "^") 
			return 3
		end

		return -1
	end

	def isOperator(text) 
		if (self.precedence(text) != -1) 
			return true
		end

		return false
	end

	#  Converting the given infix 
	#  expression to prefix expression
	def infixToPrefix(infix) 
		#  Get the size
		size = infix.length
		#  Create stack object
		s = MyStack.new()
		op = MyStack.new()
		#  Some useful variables which is using of to 
		#  storing current result
		auxiliary = ""
		op1 = ""
		op2 = ""
		isValid = true
		i = 0
		while (i < size && isValid) 
			if (infix[i] == '(') 
				op.push("(")
			elsif(self.isOperator(infix[i].to_s) == true) 
				#  When get a operator 
				while (s.size > 1 && self.precedence(
                  infix[i].to_s) <= self.precedence(op.peek())) 
					op1 = s.pop()
					op2 = s.pop()
					auxiliary = op.pop() + op2 + op1
					#  Add new result into stack
					s.push(auxiliary)
				end

				auxiliary = infix[i].to_s
				op.push(auxiliary)
			elsif(infix[i] == ')') 
				if (s.size > 1) 
					while (s.size > 1 && op.peek() != "(") 
						op1 = s.pop()
						op2 = s.pop()
						auxiliary = op.pop() + op2 + op1
						#  Add new result into stack
						s.push(auxiliary)
					end

					op.pop()
				else
 
					isValid = false
				end

			elsif((infix[i] >= '0' && infix[i] <= '9') || 
                  (infix[i] >= 'a' && infix[i] <= 'z') || 
                  (infix[i] >= 'A' && infix[i] <= 'Z')) 
				auxiliary = infix[i].to_s
				s.push(auxiliary)
			else
 
				isValid = false
			end

			i += 1
		end

		if (isValid == false) 
			print("Invalid infix : ", infix)
		else
 
			#  Display result
			print("\n Infix   : ", infix)
			print("\n Prefix  : ", s.pop())
		end

	end

end

def main() 
	task = Conversion.new()
	#  Test
	infix = "((a*b)+(c^d))"
	task.infixToPrefix(infix)
	infix = "((a/(b-c+d))*(e-a)*c)"
	task.infixToPrefix(infix)
end

main()

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd
 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment