Skip to main content

Evaluate postfix expression using stack in golang

Go program for Evaluate postfix expression using stack. Here problem description and explanation.

package main
import "fmt"
/* 
    Go program for 
    Evaluate postfix expression
*/
// Stack Node
type StackNode struct {
	operand int
	next * StackNode
}
func getStackNode(operand int, 
                  top * StackNode) * StackNode {
	// return new StackNode
	return &StackNode {
		operand,
		top,
	}
}
type MyStack struct {
	top * StackNode
	count int
}
func getMyStack() * MyStack {
	// return new MyStack
	return &MyStack {
		nil,
		0,
	}
}
// Returns the number of element in stack
func(this MyStack) isSize() int {
	return this.count
}
func(this MyStack) isEmpty() bool {
	if this.isSize() > 0 {
		return false
	} else {
		return true
	}
}
// Add a new element in stack
func(this *MyStack) push(value int) {
	// Make a new stack node
	// And set as top
	this.top = getStackNode(value, this.top)
	// Increase node value
	this.count++
}
// Remove a top element 
func(this *MyStack) pop() int {
	var value int = this.peek()
	if this.isEmpty() == false {
		this.top = this.top.next
		// Reduce the size
		this.count--
	}
	return value
}
// Used to get top element of stack
func(this MyStack) peek() int {
	if !this.isEmpty() {
		return this.top.operand
	} else {
		return 0
	}
}

func evaluate(e string) {
	// Get the length of expression
	var size int = len(e)
	var a int = 0
	var b int = 0
	var s * MyStack = getMyStack()
	var isVaild bool = true
	// Work with (+,-,/,*,%) operator
	for i := 0 ; i < size && isVaild ; i++ {
		if e[i] >= '0' && e[i] <= '9' {
			a = int(e[i]) - 48
			s.push(a)
		} else if s.isSize() > 1 {
			a = s.pop()
			b = s.pop()
			// Perform arithmetic operations between 2 operands
			if e[i] == '+' {
				s.push(b + a)
			} else if e[i] == '-' {
				s.push(b - a)
			} else if e[i] == '*' {
				s.push(b * a)
			} else if e[i] == '/' {
				s.push(b / a)
			} else if e[i] == '%' {
				s.push(b % a)
			} else {
				// When use other operator
				isVaild = false
			}
		} else if s.isSize() == 1 {
			// Special case  
			// When use +, - at the beginning
			if e[i] == '-' {
				a = s.pop()
				s.push(-a)
			} else if e[i] != '+' {
				// When not use  +,-
				isVaild = false
			}
		} else {
			isVaild = false
		}
	}
	if isVaild == false {
		// Possible case use other operators
		// 1) When using special operators
		// 2) Or expression is invalid
		fmt.Println(e, " Invalid expression ")
		return
	}
	fmt.Println(e, " = ", s.pop())
}
func main() {
	
	// Execute the following expression
	// (1+2)*(3+5)
	evaluate("12+35+*")
	// -((7*2) + (6/2) + 4)
	evaluate("72*62/+4+-")
}

Output

12+35+*  =  24
72*62/+4+-  =  -21




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