Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- #include <stdbool.h>
- #include <memory.h>
- struct Stack{
- int capacity;
- int size;
- int back;
- int* data;
- };
- typedef struct Stack Stack;
- Stack* CreateStack(int initCapacity){
- Stack* stack = (Stack*)malloc(sizeof(Stack));
- stack->capacity = initCapacity;
- stack->size = 0;
- stack->data = (int*)malloc(initCapacity * sizeof(int));
- stack->back = 0;
- return stack;
- }
- void DestroyStack(Stack* stack){
- free(stack->data);
- stack->capacity = 0;
- stack->size = 0;
- stack->back = 0;
- free(stack);
- return;
- }
- void Extend(Stack* stack){
- assert(stack->size <= stack->capacity);
- if(stack->size < stack->capacity){
- return;
- }
- int* newData = (int*)realloc(stack->data, (2 * stack->capacity) * sizeof(int));
- stack->data = newData;
- stack->capacity = 2 * stack->capacity;
- return;
- }
- void Shrink(Stack* stack){
- if(stack->size >= (stack->capacity / 4)){
- return;
- }
- int* newData = (int*)realloc(stack->data, (stack->capacity / 2) * sizeof(int));
- stack->data = newData;
- stack->capacity = stack->capacity / 2;
- return;
- }
- void PushBack(Stack* stack, int element){
- stack->data[stack->size] = element;
- if(stack->size == 0){
- stack->back = 0;
- }
- ++stack->size;
- ++stack->back;
- Extend(stack);
- return;
- }
- void PopBack(Stack* stack){
- assert(stack->size > 0);
- stack->data[stack->size - 1] = 0;
- --stack->back;
- --stack->size;
- Shrink(stack);
- return;
- }
- bool IsEmpty(Stack* stack){
- return(stack->size == 0);
- }
- void StackState(Stack* stack){
- printf("%d %d %d \n", stack->capacity, stack->size, stack->back);
- for(int i = 0; i < stack->size; ++i){
- printf("%d \n", stack->data[i]);
- }
- return;
- }
- bool IsLeft(int chr){
- return((chr == '(' || (chr == '[') || (chr == '{')));
- }
- int Pair(int chr){
- assert(chr == ')' || chr == '(' || chr == '{' || chr == '}' || chr == '[' || chr == ']' || chr == 10 || chr == EOF);
- if(chr == '('){
- return ')';
- }
- if(chr == ')'){
- return '(';
- }
- if(chr == '['){
- return ']';
- }
- if(chr == ']'){
- return '[';
- }
- if(chr == '{'){
- return '}';
- }
- if(chr == '}'){
- return '{';
- }
- return -1;
- }
- int main() {
- Stack* stack = CreateStack(8);
- // for(int i = 0; i < 10; ++i){
- // PushBack(stack, i);
- // StackState(stack);
- // }
- // for(int i = 0; i < 5; ++i){
- // PopBack(stack);
- // StackState(stack);
- // }
- int chr = 0;
- // chr = getchar();
- // chr = Pair(chr);
- // putchar(chr);
- while(chr != EOF){
- chr = getchar();
- if(IsEmpty(stack)){
- PushBack(stack, chr);
- StackState(stack);
- }
- else{
- if (IsLeft(chr) && chr == Pair(stack->data[stack->back])){
- PopBack(stack);
- }
- else{
- PushBack(stack, chr);
- }
- }
- }
- for(int i = 0; i < stack->size; ++i){
- putchar(stack->data[i]);
- }
- printf("%d", Pair('('));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement