C++

Forum

 
Stack

pacman169 (374)

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
MiiNiPaa (8886)
What should change after your swap function?
pacman169 (374)
I don`t understand the question. Read the code comments.
MiiNiPaa (8886)
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.
pacman169 (374)
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);
   
  }
MiiNiPaa (8886)
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);
}
pacman169 (374)
Why without popping? In real use case you would pop them.


Because the exercise states so. How can I do that?
MiiNiPaa (8886)
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();
}

pacman169 (374)
Can you write in C? I don`t know C++.
MiiNiPaa (8886)
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
pacman169 (374)
How do I print the top element of the stack without popping it?
MiiNiPaa (8886)
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?
pacman169 (374)
The swap function does`t work: for example:

Input: 4 8 9 ~


9

8

4

It prints the elements in same order. Why?
MiiNiPaa (8886)
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
Topic archived. No new replies allowed.