Stack

Aug 11, 2015 at 6:46pm

I have a very simple implementation of stack in c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#define MAXVAL 100  /* maximum depth of val stack */




int sp = 0;           /* next free stack position */
double val[MAXVAL];   /* value stack */  

 void swap(void)               /* Swap two top elements of stack */
  {
	  double first = pop();
	  double second = pop();
	  
	  push(second);
	  push(first);
   
  }
	   
  
 



How can I test if the swap function works?
Last edited on Aug 11, 2015 at 6:48pm
Aug 11, 2015 at 6:53pm
What should change after your swap function?
Aug 11, 2015 at 8:51pm
I don`t understand the question. Read the code comments.
Aug 11, 2015 at 8:58pm
Answer to this question is answer to your problem: you just need to check if stack state after swap is expected one.
In your case you need to insert two elements in order, perform swap and check if two first elements of stack are in expected order.
Aug 12, 2015 at 8:54pm
I guess I need to print the top two elements of the stack without popping them?
How can I do that?

Here is my code so far:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

......

/* reverse Polish calculator */

 int main()
 {
 
     int type;
	 double op2;
	 char s[MAXOP];
	 
 while ((type = getop(s)) != EOF) {
     switch (type)  {
	 
	 case NUMBER:
	      push (atof(s));
		  break;
		  
     case '+':
	 
	     push( pop() + pop() );
		 break;
		 
		 
	 case '*':
	 
	    push(pop() * pop());
	    break;
		
	 case '-':
	   
	 op2 = pop();                        /*   Addition on the real numbers is commutative because for any real numbers s,t, it is true that s+t=t+s.
                                           Addition and multiplication are commutative operations but subtraction and division are not. */
	 push(pop() - op2);
	 break;
	 
	 case '/':
	 
	 op2 = pop();
	 if (op2 != 0.0)
	     push(pop() / op2);
	 
	 else 
		  printf("error: zero divisor\n");
	 break;
	 
	 case '%':
	 
	 op2 = pop();
	    
	 push(fmod(pop(), op2));
	 break;
	 
	 case '~':
	 
	 swap();
	 break;
	 
	 
	  case '\n':
	 
     printf("\t%.8g\n" , pop());
	 break;
	 
	 default:
	 printf("error: unknown command %s\n", s);
	 break;
	 
     }
	 
   }
   return 0;
  
 }
	 
	 
	
	
#define MAXVAL 100  /* maximum depth of val stack */




int sp = 0;           /* next free stack position */
double val[MAXVAL];   /* value stack */  
	 
 /* push : push f onto value stack */
 
 void push(double f)
 {
    if (sp < MAXVAL)	
		val[sp++] = f;
	
	else
		printf("error: stack full, can`t push %g\n", f);
	
 }
 
 
 
 /* pop: pop and return top value from stack */
 
  double pop(void)
  {
  	
	  if (sp > 0)
		  return val[--sp];
	  else {
		  printf("error: stack empty\n");
		  return 0.0;
	  }
	  
  }
  
  
  void swap(void)               /* Swap two top elements of stack */
  {
	  double first = pop();
	  double second = pop();
	  
	  push(second);
	  push(first);
   
  }
	   
  
 
Aug 12, 2015 at 10:05pm
I guess I need to print the top two elements of the stack without popping them?
Why without popping? In real use case you would pop them.

So your test can be something like:

1
2
3
4
5
6
7
8
9
10
bool swap_test()
{
    push(42);
    push(10);
    //top: 10 next: 42
    swap();
    //expect to: 42, next: 10
    //Short-circuit evaluation:
    return (pop() == 42) && (pop() == 10);
}
Aug 13, 2015 at 10:36am
Why without popping? In real use case you would pop them.


Because the exercise states so. How can I do that?
Aug 13, 2015 at 10:47am
Well, then you either need to inspect underlying stack data or use swap+inspect top element;

Example of test using standard stack:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <stack>

template<typename T>
void swap_top(std::stack<T>& stack)
{
	auto t = stack.top();
	stack.pop();
	auto b = stack.top();
	stack.pop();
	stack.push(t);
	stack.push(b);
}

bool test_swap()
{
	std::stack<int> foo;
	foo.push(1); foo.push(2);
	bool pass = foo.top() == 2;
	swap_top(foo);
	//check if swap took place
	pass = pass && foo.top() == 1;
	//check if bottom value is not damaged
	swap_top(foo);
	pass = pass && foo.top() == 2;

	return pass;
}


int main()
{
	std::cout << test_swap();
}

Aug 13, 2015 at 10:59am
Can you write in C? I don`t know C++.
Aug 13, 2015 at 11:04am
I am going to write in pseudocode as C does not have a standard stack.
#add two elements a and b on stack
#swap elements
#check if a is currently on top
#swap elements
#check if b is currently on top
Aug 13, 2015 at 7:50pm
How do I print the top element of the stack without popping it?
Aug 13, 2015 at 7:52pm
YOu have three ways to do so:
1) Pop element and insert it back
2) Implement function which does that
3) Put your hands elbow deep in innards of stack and take value directly

Slight hint: what happens if you remove -- from line 108 in your code?
Aug 14, 2015 at 11:39am
The swap function does`t work: for example:

Input: 4 8 9 ~


9

8

4

It prints the elements in same order. Why?
Aug 14, 2015 at 11:56am
So you finaly noticed it.

Look what you have:
Before swap: 
4 8 9 >
after line 12:
first = 9
4 8 >
after line 13:
first = 9
second = 8
4 >
after line 15: push(second)
first = 9
4 8 >
after line 16: push(first)
4 8 9 >
See the problem now?
Hint: liik at my swap implementation (lines 7-12)
Last edited on Aug 14, 2015 at 11:56am
Topic archived. No new replies allowed.