As you can see in the “ABOUT” menu item I am an undergraduated student at Universidade da Beira Interior and I’m one of the founders of the Programming Club. In the programming club we learn some algorithms that we don’t usually learn in class. Each month we gather and discuss a subject, for each subject we choose one problem and try to solve it until the next meeting. I will be posting here the subject discussed on every meeting and then I will post the solution to each problem.
Hope you learn something from this…
Subject: Stack Programming
Problem: RPN calculator
A RPN (Reverse Polish Notation) calculator uses post-fixes operands. For example, to add two numbers, you get one, then the other and, finally, the addition operator:
The previous example is the operation 5 – 2 in RPN notation.
Problem
In this problem, we want to implement a simple RPN calculator with the four basic arithmetic operators (+, -, * and /) and the assignment (=). The assignment returns the assigned value. The tool should read from STDIN an expression by line, and write to STDOUT a result by line. Consider that all lines have the correct syntax.
Input
The input consists of a sequence of expressions. Each expression is contained in a single line. Variables can be defined and used in the lines following their definition.
Output
The output contains the results of evaluating each one of the expressions (one per line).
Sample Input
2 2 + 3 - 1 2 3 * + a 10 = a 2 / 2 2 + + -2 -3 + a 10 = b 5 = +
Sample Output
1 7 10 9 -5 15
Solution:
import java.util.Stack;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Hashtable;
import java.util.Scanner;
/**
* <p>Title: Reverse Polish Calculator</p>
*
* <p>Company: Clube da Programação – Universidade da Beira Interior</p>
*
* @author Tiago Barbosa
* @version 1.0
*/
public class rpn {
Hashtable<String, Integer> varLst;
ArrayList<Object> res;
public rpn() {
this.varLst = new Hashtable<String, Integer> ();
this.res = new ArrayList<Object> ();
}
public void devolveResultado(String s) {
StringTokenizer st = new StringTokenizer(s);
Stack<Object> stack = new Stack<Object> ();
while (st.hasMoreTokens()) {
String token = st.nextToken();
try {
stack.push(new Integer(token));
}
catch (NumberFormatException ex) {
int v1 = 0, v2 = 0;
String v3, v4;
switch (token.charAt(0)) {
case ‘+’:
Object a, b;
b = stack.pop();
a = stack.pop();
if(varLst.containsKey(b)==true){
v2=((Integer)varLst.get((String)b)).intValue();
}
else{
v2=((Integer)b).intValue();
}
if(varLst.containsKey(a)==true){
v1=((Integer)varLst.get((String)a)).intValue();
}
else{
v1=((Integer)a).intValue();
}
stack.push(v1 + v2);
break;
case ‘-’:
b = stack.pop();
a = stack.pop();
if(varLst.containsKey(b)==true){
v2=((Integer)varLst.get((String)b)).intValue();
}
else{
v2=((Integer)b).intValue();
}
if(varLst.containsKey(a)==true){
v1=((Integer)varLst.get((String)a)).intValue();
}
else{
v1=((Integer)a).intValue();
}
stack.push(v1 – v2);
break;
case ‘*’:
b = stack.pop();
a = stack.pop();
if(varLst.containsKey(b)==true){
v2=((Integer)varLst.get((String)b)).intValue();
}
else{
v2=((Integer)b).intValue();
}
if(varLst.containsKey(a)==true){
v1=((Integer)varLst.get((String)a)).intValue();
}
else{
v1=((Integer)a).intValue();
}
stack.push(v1 * v2);
break;
case ‘/’:
b = stack.pop();
a = stack.pop();
if(varLst.containsKey(b)==true){
v2=((Integer)varLst.get((String)b)).intValue();
}
else{
v2=((Integer)b).intValue();
}
if(varLst.containsKey(a)==true){
v1=((Integer)varLst.get((String)a)).intValue();
}
else{
v1=((Integer)a).intValue();
}
stack.push(v1 / v2);
break;
case ‘=’:
b=stack.pop();
a=stack.pop();
try{
v2 = ( (Integer) b).intValue();
v3 = ( (String) a);
}
catch(NumberFormatException e){
v2 = ( (Integer) a).intValue();
v3 = ( (String) b);
}
catch(Exception e){
v3 = ( (String) a);
v2 = ((Integer)varLst.get((String)b)).intValue();
}
if (varLst.get(v3) != null) {
varLst.remove(v3);
varLst.put(v3, v2);
stack.push(v2);
}
else {
varLst.put(v3, v2);
stack.push(v2);
}
break;
default:
stack.push(token);
}
}
}
res.add(stack.peek());
}
public void escrita(ArrayList a) {
for (int i = 0; i < a.size(); i++) {
System.out.println(a.get(i));
}
}
public static void main(String[] args) {
rpn rpn = new rpn();
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
rpn.devolveResultado(in.nextLine());
}
rpn.escrita(rpn.res);
}
}
Subject: Dynamic Programming
Problem:Assembly Line Scheduling
We have two assembly lines as you can see in the image shown above. Every move in each assembly line has its weight and every move between lines has its weight also. The purpose of this problem is to find which is the path with less weight…using dynamic programming. Enjoy…
Sample Input
6 7 9 3 4 8 4 8 5 6 4 5 7 2 2 3 1 3 4 3 4 2 1 2 2 1 2
Sample Output
linha 1, posto 6
linha 2, posto 5
linha 2, posto 4
linha 1, posto 3
linha 2, posto 2
linha 1, posto 1
Solution:
#include<stdio.h>
int main(){
int nStations,i,j,ind;
int **a,**t,**r1,**r2;
scanf(“%d”,&nStations);
a=(int**)malloc(2*sizeof(int*));
a[0]=(int*)malloc(nStations*sizeof(int));
a[1]=(int*)malloc(nStations*sizeof(int));
t=(int**)malloc(2*sizeof(int *));
t[0]=(int*)malloc((nStations+1)*sizeof(int));
t[1]=(int*)malloc((nStations+1)*sizeof(int));
r1=(int**)malloc(2*sizeof(int *));
r1[0]=(int*)malloc((nStations+1)*sizeof(int));
r1[1]=(int*)malloc((nStations+1)*sizeof(int));
r2=(int**)malloc(2*sizeof(int *));
r2[0]=(int*)malloc((nStations)*sizeof(int));
r2[1]=(int*)malloc((nStations)*sizeof(int));
for (i = 0; i < 2; i++){
for (j = 0; j <nStations; j++){
scanf(“%d”, &a[i][j]);
}
}
for (i = 0; i < 2; i++){
for (j = 0; j < (nStations + 1); j++){
scanf(“%d”, &t[i][j]);
}
}
//função que resolve
for(j=0;j<nStations;j++){
if(j==0){
r1[0][0]=t[0][0]+a[0][0];
r1[1][0]=t[1][0]+a[1][0];
}
else{
//para a linha 1
if(r1[1][j-1]+t[1][j]+a[0][j]<r1[0][j-1]+a[0][j]){
r1[0][j]=r1[1][j-1]+t[1][j]+a[0][j];
r2[0][j]=2;
}
else{
r1[0][j]=r1[0][j-1]+a[0][j];
r2[0][j]=1;
}
//para a linha 2
if(r1[0][j-1]+t[0][j]+a[1][j]<r1[1][j-1]+a[1][j]){
r1[1][j]=r1[0][j-1]+t[0][j]+a[1][j];
r2[1][j]=1;
}
else{
r1[1][j]=r1[1][j-1]+a[1][j];
r2[1][j]=2;
}
}
}
//somar pesos finais
r1[0][nStations]=r1[0][nStations-1]+t[0][nStations];
r1[1][nStations]=r1[1][nStations-1]+t[1][nStations];
//mostrar tempo
if(r1[0][nStations]<r1[1][nStations])
printf(“\ntempo: %d\n\n”,r1[0][nStations]);
else
printf(“\ntempo: %d\n\n”,r1[1][nStations]);
//mostrar caminho optimal
printf(“Caminho optimal\n\n”);
if(r1[0][nStations]<r1[1][nStations])
{
ind=0;
for(i=nStations-1;i>=0;i–){
printf(” linha %d posto %d\n”,ind+1,i+1);
ind=r2[ind][i]-1;
}
}
else
{
ind=1;
for(i=nStations-1;i>=0;i–){
printf(” linha %d posto %d\n”,ind+1,i+1);
ind=r2[ind][i]-1;
}
}
return 0;
}
