Enjoy implementing calculator with stack and recursive call

This is a picture of unique shoji :)

1. Introduction

I enjoyed implementing a calculator. It can calculate as follows :)

1 + 2                       Answer: 3
1 + 2 x (10 + 1)        Answer: 23
(1 + 1) x (1 + 2)       Answer: 6

2. Program

2.1. Input

As for a program input, I supposed like the following letter string.

[Input]
1+2
1+1*(10+0)
(1+1)*(1+2)

2.2. Output

As for a program output, it's simply its calculation result.
In the above cases, the output is as follows.

[Output]
3
11
6

2.3. Implementation

I can simply implement by using a stack and a recursive call as follows.
Thanks to the recursive call, we can calculate the text within parentheses :)

Main.java

package org.inut;

import java.util.*;

class Main { 
    public void pushCalcStack(int currNum, char operator, Deque<Integer> calcStack) {
        if (operator == '+') {
            calcStack.push(currNum);
        } else if (operator == '-') {
            calcStack.push(-currNum);
        } else if (operator == '*') {
        int prevNum = calcStack.pop();
            calcStack.push(prevNum * currNum);
        } else if (operator == '/') {
        int prevNum = calcStack.pop();
        calcStack.push(prevNum / currNum);
        }
    }
 
    public int simpleCalc(String str) {
        Deque<Integer> calcStack = new ArrayDeque();
        int calcResult = 0;
        char operator = '+';
        int currNum = 0;
        int currIndex = 0;
        boolean isParentheses = false;
        int startIndex = 0;
     
        for (char letter : str.toCharArray()) {
            if (Character.isDigit(letter)) {
                currNum = 10 * currNum + letter - '0';
            } else {
                if (letter == '(') {
                    isParentheses = true;
                    startIndex = currIndex + 1;
                }
                if (letter == ')') {
                    isParentheses = false;
                    currNum = simpleCalc(s.substring(startIndex, currIndex));
                }
                if (!isParentheses) {
                    pushCalcStack(currNum, operator, calcStack);
                    operator = letter;
                    currNum = 0;
                }
            }
            currIndex++;
        }
     
        if (currNum != 0)
        pushCalcStack(currNum, operator, calcStack);
     
        for (int num : calcStack)
            calcResult += num;
     
        return  calcResult;
    }
 
    public static void main(String[] args) {
        String input = "2*(1+2)/2-1*(5*3)";
     
        int calcResult = new Main().simpleCalc(input);
        System.out.println(calcResult);
    }
}

3. Extension

If we want to use other parentheses such as '{' and '[', we can do that by using a recursive call and modifying some conditions :)

Vertexes on the contour formed by n rectangles

This is Manila. I met my best friends :)

1. Introduction

In this article, I consider a simple program outputting vertexes on the contour formed by n rectangles.

The locations and height of n rectangles are given like Figure 1, 2, 3.
It is guaranteed that 2 ≤ n ≤ Max of Integers.

I assumed the following as for vertex information.

[Assumption]
1. I suppose that the vertex information of each rectangles is represented by array of integers [lx, rx, ly, ry], [lx', rx', ly', ry'], ... .

2. It is guaranteed that 0 ≤ lx < rx ≤ Max of Integer and 0 ≤ ly < hy ≤ Max of Integer.

2. Program

2.1. Input

And as for a program input, I supposed the following list.

[Input]
{(lx, rx, ly, hy), (lx', rx', Lly', hy'), ...}

2.2. Output

As for a program output, I suppose to output the list of vertexes on the contour formed by these rectangles like Figure 1', 2', 3'.

[Output]
Figure1: {(lx,ly), (rx,ly), (rx,ly'), (rx',ly'), (lx,hy), (lx',hy), (lx',hy'), (rx',hy')}
Figure2: {(lx,ly), (lx',ly), (lx',ly'), (rx',ly'), (lx,hy), (rx,hy), (rx,hy'), (rx',hy')}

Figure3: {(lx,ly), (rx',ly'), (lx,ly), (rx',ly')}

2.3. Implementation

For example, I can simply implement as follows.

Main.java

package org.inut;

import java.util.*;

class Main {
  int lx = 0;
  int rx = 0;
  int ly = 0;
  int hy = 0;

  public List<List<Integer>> seekVertexes(List<List<Integer>> input, List<List<Integer>> outputLowerSide, List<List<Integer>> outputUpperSide) {
    for (List<Integer> list : input) {
      int newLx = list.get(0);
      int newRx = list.get(1);
      int newLy = list.get(2);
      int newHy = list.get(3);

      // seek vertexes on the lower side
      if (ly != newLy) {
        if (outputLowerSide.isEmpty()) {
          outputLowerSide.add(new ArrayList<Integer>() {{add(newLx); add(newLy); }});
          lx = newLx;
          ly = newLy;
        } else {
          if (ly < newLy) {
            outputLowerSide.add(new ArrayList<Integer>() {{ add(rx); add(ly); }});
            outputLowerSide.add(new ArrayList<Integer>() {{ add(rx); add(newLy); }});
          } else if (ly > newLy) {
            outputLowerSide.add(new ArrayList<Integer>() {{ add(newLx); add(ly); }});
            outputLowerSide.add(new ArrayList<Integer>() {{ add(newLx); add(newLy); }});
          }

          lx = newLx;
          ly = newLy;
        }
      }

      // seek vertexes on the upper side
      if (hy != newHy) {
        if (outputUpperSide.isEmpty()) {
          outputUpperSide.add(new ArrayList<Integer>() {{add(newLx); add(newHy); }});
          lx = newLx;
          hy = newHy;
        } else {
           if (hy > newHy) {
             outputUpperSide.add(new ArrayList<Integer>() {{ add(rx); add(hy); }});
             outputUpperSide.add(new ArrayList<Integer>() {{ add(rx); add(newHy); }});
           } else if (hy < newHy) {
             outputUpperSide.add(new ArrayList<Integer>() {{ add(newLx); add(hy); }});
             outputUpperSide.add(new ArrayList<Integer>() {{ add(newLx); add(newHy); }});
           }

            lx = newLx;
            hy = newHy;
        }
      }

      rx = newRx;
    }

    outputLowerSide.add(new ArrayList<Integer>() {{add(rx); add(ly); }});
    outputUpperSide.add(new ArrayList<Integer>() {{add(rx); add(hy); }});

    List<List<Integer>> result = new ArrayList<>();
    result.addAll(outputLowerSide);
    result.addAll(outputUpperSide);

    return result;

  }

  public static void main(String args[]) {
    List<List<Integer>> input = new ArrayList<>();
    input.add(Arrays.asList(1,3,1,3));
    input.add(Arrays.asList(2,5,2,5));
    input.add(Arrays.asList(4,7,1,4));

    List<List<Integer>> outputLowerSide = new ArrayList<>();
    List<List<Integer>> outputUpperSide = new ArrayList<>();
    List<List<Integer>> result = new Main().seekVertexes(input, outputLowerSide, outputUpperSide);

    for (List<Integer> elm : result) {
      System.out.println(elm);
    }
  }
}

3. Sort and Performance

This program will work well.

However, if sort is needed and n is large number, I want to come to use some sort algorithm to get the good performance. For example, it's a merge sort algorithm :)