Question

****C++, put both of them in to one main method, make sure to start with main class, if I get a screenshot of the output as well.

thank you

(3) Use singly linked lists to implement integers of unlimited size. Each node of the list should store one digit of the integer. You should implement addition, subtraction, multiplication, and exponentiation operations. Limit exponents to be positive integers. What is the asymptotic running time for each of your operations, expressed in terms of the number of digits for the two operands of each function?

(4) Implement a program that can input an expression in postfix notation and output its value.

Answer 1

3)

//This program will add, substract and multiply two lists
//Lists are defined inside program

class LinkedList
{
    static Node head1, head2;
    static class Node {

        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    /* Adds contents of two linked lists and return the head node of resultant list */
    Node addTwoLists(Node first, Node second) {
        Node res = null; // res is head node of the resultant list
        Node prev = null;
        Node temp = null;
        int carry = 0, sum;

        while (first != null || second != null) //while both lists exist
        {

            sum = carry + (first != null ? first.data : 0)
                    + (second != null ? second.data : 0);

            // update carry for next calulation
            carry = (sum >= 10) ? 1 : 0;

            // update sum if it is greater than 10
            sum = sum % 10;

            // Create a new node with sum as data
            temp = new Node(sum);

            // if this is the first node then set it as head of
            // the resultant list
            if (res == null) {
                res = temp;
            } else // If this is not the first node then connect it to the rest.
            {
                prev.next = temp;
            }

            // Set prev for next insertion
            prev = temp;

            // Move first and second pointers to next nodes
            if (first != null) {
                first = first.next;
            }
            if (second != null) {
                second = second.next;
            }
        }

        if (carry > 0) {
            temp.next = new Node(carry);
        }

        // return head of the resultant list
        return res;
    }

    //function to subtract given lists
    Node subtract(Node first, Node second, int borrow) {
        Node result = new Node(borrow);
        int value = borrow;

        //return null when both list are null
        if (first == null && second == null && borrow == 0)
            return null;

        if (first.data >= second.data) {
            value += first.data - second.data;
            borrow = 0;
        } else {
            if (first.next != null) {
                value += (first.data) + 10 - second.data;
                borrow = -1;
            } else {
                value += (first.data) + 10 - second.data;
                value = value * (-1);
                borrow = 0;
            }
        }
        result.data = value;

        //Recurse
        if (first.next != null || second.next != null || borrow < 0) {
            Node more = subtract(first.next != null ? first.next : null,
                    second.next != null ? second.next : null,
                    borrow < 0 ? -1 : 0);

            result.next = more;
        }
        return result;
    }

    //function to convert list into number
    static int getNumber(Node list) {
        int number = 0;
        while (list != null) {
            number = 10 * number + list.data;
            list = list.next;
        }
        return number;
    }

    //function to traverse a list
    static Node process(Node list) {
        Node head = list;
        int carry = 0, i = 0;

        while (head != null && head.next != null) {
            i = head.data;
            head.data = (carry + i) % 10;
            carry = (i + carry) / 10;
            head = head.next;
        }
        head.data = head.data + carry;
        return reverse(list);
    }

    //function to reverse the given list
    static Node reverse(Node list) {
        if (list == null)
            return null;

        Node current = list, previous = null, forward;
        while (current != null) {
            forward = current.next;
            current.next = previous;
            previous = current;
            current = forward;
        }
        return previous;
    }

    static Node multiply(Node first, Node second) {
        //When both lists are null, return null
        if (first == null || second == null)
            return null;

        int number = getNumber(first);  //convert one list into number

        //traverse the second list and multiply the number with the current element of the list and store in the new list.
        Node current = second;
        Node result = null;
        while (current != null) {
            if (result == null) {
                result = new Node(current.data * number);
            } else {
                //multiply current element with the "number" and store in the new list node
                Node temp = new Node(current.data * number);
                temp.next = result;
                result = temp;
            }
            current = current.next;
        }
        return process(result);
    }

    /*function to print a linked list */
    void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // creating first list
        list.head1 = new Node(7);
        list.head1.next = new Node(5);
        list.head1.next.next = new Node(9);
        list.head1.next.next.next = new Node(4);
        list.head1.next.next.next.next = new Node(6);
        System.out.print("First List is ");
        list.printList(head1);

        // creating seconnd list
        list.head2 = new Node(8);
        list.head2.next = new Node(4);
        list.head2.next.next = new Node(8);
        list.head2.next.next.next = new Node(4);
        list.head2.next.next.next.next = new Node(4);
        System.out.print("Second List is ");
        list.printList(head2);

        // add the two lists and see the result
        Node add = list.addTwoLists(head1, head2);
        System.out.print("\r\nResultant List after Addition is : ");
        list.printList(add);

        Node sub = list.subtract(head1, head2, 0);
        System.out.print("\r\nResultant List after Substraction is : ");
        list.printList(sub);

        Node multiply = list.multiply(head1, head2);
        System.out.print("\r\nResultant List after Multiplication is : ");
        list.printList(multiply);
    }
}

I have pasted the output below

4)

#include<iostream>
#include "stack.h"

using namespace std;

int postfixEval(const char *postfix) {
   Stack s;
   int i = 0, a, b, results;
  

   while(postfix[i] != '\0') {
       if(postfix[i] >= '0' && postfix[i] <= '9')
           s.push(postfix[i] - '0');
       else
           if (postfix[i] == '+') {
               b = s.peek();
               s.pop();
               a = s.peek();
               s.pop();
               s.push(a + b);
           }
           else if (postfix[i] == '-') {
               b = s.peek();
               s.pop();
               a = s.peek();
               s.pop();
               s.push(a - b);
           }
           else if (postfix[i] == '*') {
               b = s.peek();
               s.pop();
               a = s.peek();
               s.pop();
               s.push(a * b);
           }
           else if (postfix[i] == '/') {
               b = s.peek();
               s.pop();
               a = s.peek();
               s.pop();
               s.push(a / b);
           }
       i++;
   }

   return s.peek();
}

int main() {
   string s;
   cout << "Enter postfix expression: ";
   cin >> s;
   cout << "result: " << postfixEval(s.c_str()) << endl;
}

Input:
12+
output:
3

Input:
321+*
output:
9