I do not want you to finish complete the program, i want to see a working versio

Question

I do not want you to finish complete the program, i want to see a working version for addition using stacks maybe even with linked list but if it does not need it w/e i was trying to use linked list but it became a mess. Again i dont need + * / i just want +. entering numbers into a stack and then if + is entered then it adds and pops into the next. Thanks

The program reads the input from a user character by character until it finds an end of line character, and recognizes operands (uninterrupted sequences of digits 0-9) and operators (+ - * / ) and puts them in a Stack.

Push 3, 5, then 2 on stack:
2
5
3
---
When the + is found, pop the 2 and 5 off the stack, add them, and push
the result back on the stack:
7
3
---
Push 2 on the stack:
2
7
3
---
When * is encountered, pop off 7 and 2, calculate 7 * 2, and push the result back on the stack, then push 5 on the stack:
5
14
3
---
When - is encountered, pop off 14 and 5, subtract 5 from 14, and push
the result on the stack, then push 2 on the stack:
2
9
3
---
The final sequence of two +'s result in the following stacks:
11
3
---
14
---
The result is 14
Some compilers translate all expressions into postfix form because they are so easy to evaluate, and some architectures have a hardware stack to facilitate this process.
The following is the algorithm for evaluating the postfix expression:
• algorithm:
operand_stack = empty stack
while (not end of input)
symbol = next input symbol
if (symbol is operand)
push(operand_stack, symbol)
else
operand2 = pop(operand_stack)
operand1 = pop(operand_stack)
result = apply symbol to operand1 and operand2
push(operand_stack, result)
return pop(operand_stack)

a) The program reads the input from a user character by character until it finds an end of line character, and recognizes operands (uninterrupted sequences of digits 0-9) and operators (+ - * / ) and puts them in a Stack. Stack should contain only integers for the operands (containing only nonnegative integers). For example if the input string is “3 14 * 5 +” the following order should be used to enter integers into the Stack: integer(3), integer(14), integer(5). Note that the following is incorrect sequence of the integers for the above string: integer(3), integer(1), Integer(4), Integer(5), since operand 14 is split to two operands!

Explanation / Answer

// C program to evaluate value of a postfix expression
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

// Stack type
struct Stack
{
   int top;
   unsigned capacity;
   int* array;
};

// Stack Operations
struct Stack* createStack( unsigned capacity )
{
   struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

   if (!stack) return NULL;

   stack->top = -1;
   stack->capacity = capacity;
   stack->array = (int*) malloc(stack->capacity * sizeof(int));

   if (!stack->array) return NULL;

   return stack;
}

int isEmpty(struct Stack* stack)
{
   return stack->top == -1 ;
}

char peek(struct Stack* stack)
{
   return stack->array[stack->top];
}

char pop(struct Stack* stack)
{
   if (!isEmpty(stack))
       return stack->array[stack->top--] ;
   return '$';
}

void push(struct Stack* stack, char op)
{
   stack->array[++stack->top] = op;
}

// The main function that returns value of a given postfix expression
int evaluatePostfix(char* exp)
{
   // Create a stack of capacity equal to expression size
   struct Stack* stack = createStack(strlen(exp));
   int i;

   // See if stack was created successfully
   if (!stack) return -1;

   // Scan all characters one by one
   for (i = 0; exp[i]; ++i)
   {
       // If the scanned character is an operand or number,
       // push it to the stack.
       if (isdigit(exp[i]))
           push(stack, exp[i] - '0');

       // If the scanned character is an operator, pop two
       // elements from stack apply the operator
       else
       {
           int val1 = pop(stack);
           int val2 = pop(stack);
           switch (exp[i])
           {
           case '+': push(stack, val2 + val1); break;
           case '-': push(stack, val2 - val1); break;
           case '*': push(stack, val2 * val1); break;
           case '/': push(stack, val2/val1); break;
           }
       }
   }
   return pop(stack);
}

// Driver program to test above functions
int main()
{
   char exp[100];
   printf("Enter the expression");
   scanf("%s",exp);
   printf ("Value of %s is %d", exp, evaluatePostfix(exp));
   return 0;
}

------------------------

output :

--------------------------

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.