// Input: nothing for the default case or // a valid infix expression where all values // are zero or positive integers using // parentheses, addition, subtraction, // multiplication, or division. // Created for this challenge: // https://www.sololearn.com/post/133717 // Long Form Math // Write program that takes multiple lines of // simple expressions (two operands and one // operator) and shows all the work. The // operands should be operated on with integer // operators only and all results must be // zero or positive. The operators supported // must include addition, subtraction, // multiplication, and division. You must show // all borrowing or carrying operations and // explictly show converting multiple digits // in a column to a single one with an // operation. See my examples for more // details // Input: // 45*19 // 856/19 // Output: // 45 // *19 // --- // 45(5*9) // 360(40*9) // 50(5*10) // +400(40*10) // ---- // 5(5+0+0+0) // 150(40+60+50+0) // +700(0+300+0+400) // ---- // 5(5+0+0) // 50(0+50+0) // +800(0+100+700) // ---- // 855 // 45r1 // ---- // 19|856 // 360(9*40) // -400(10*40) // ---- // 6(6-0-0) // -10(50-60-0) // +100(800-300-400) // ---- // 6(6+0+0) // + 90(0-10+100) // ---- // 96 // 45(9*5) // - 50(10*5) // ---- // 1(6-5-0) // + 0(90-40-50) // ---- // 1 // Bonus: support complex expressions with the // output of one expression being fed into the // next. Division's remainders are tossed to // stay with integers. Parentheses must be // supported with normal operator precedence. // Input: // (45*19+1)/19 // Output: // 45 // *19 // --- // 45(5*9) // 360(40*9) // 50(5*10) // +400(40*10) // ---- // 5(5+0+0+0) // 150(40+60+50+0) // +700(0+300+0+400) // ---- // 5(5+0+0) // 50(0+50+0) // +800(0+100+700) // ---- // 855 // 855 // + 1 // ---- // 6(5+1) // 50(50+0) // +800(800+0) // ---- // 856 // 45r1 // ---- // 19|856 // 360(9*40) // -400(10*40) // ---- // 6(6-0-0) // -10(50-60-0) // +100(800-300-400) // ---- // 6(6+0+0) // + 90(0-10+100) // ---- // 96 // 45(9*5) // - 50(10*5) // ---- // 1(6-5-0) // + 0(90-40-50) // ---- // 1 // Method to extend Int class to return the // number of columns needed to display the // value. fun Int.size() = "$this".length // Method to extend Int class with generating // a power as requested. fun Int.pow(exponent: Int) = Math.pow(this.toDouble(), exponent.toDouble()).toInt() // Method to extend Int class with generating // a list of digits. Size is the number of // columns desired. fun Int.digits(size: Int = this.size()) = List(size) { this/(10.pow(size-it-1))%10* (10.pow(size-it-1)) } // Function to convert an infix expression // string to postfix form string from here: // https://code.sololearn.com/cF3lnVVoR6hF // Based on the rules listed here: // http://csis.pace.edu/~wolf/CS122/infix-postfix.htm fun convert(string: String): String { // Make sure there are spaces around the // operators. Remove any unneeded spaces. var infix = string.replace("+", " + ") infix = infix.replace("-", " - ") infix = infix.replace("*", " * ") infix = infix.replace("/", " / ") infix = infix.replace("(", "( ") infix = infix.replace(")", " )") infix = infix.replace(Regex(" +"), " ") infix = infix.replace(Regex("^ "), "") infix = infix.replace(Regex(" $"), "") // Allocate our empty stack and result string. // For each token in our infix expression, // process it. val postfix = mutableListOf() var string = "" for (item in infix.split(" ")) { when (item) { // When we have our lower precedence // operators, deal with them. "+", "-" -> // If the stack is empty or the // top of the stack is a left // parentheses, we haven't seen // two operands so this operator // must be pushed on the stack. if (postfix.isEmpty() || postfix.last() == "(") postfix.add(item) // Otherwise, if the top of the // stack is a higher precedence, // we have the two operands needed // so we can deal with them now. // While our stack is not empty // & the top of the stack is a higher // precedence, pop the operator and // add it to the result string. After // which, we can push the new operator. else if (postfix.last() in listOf("*", "/")) { while (postfix.isNotEmpty() && postfix.last() in listOf("*", "/")) { val op = postfix.removeAt(postfix.size-1) string += " $op" } // while postfix.add(item) // Otherwise, we got a lower precedence // operator on the stack so pop it, // add it to our result string, and // finish by pushing our new operator. } else { val op = postfix.removeAt(postfix.size-1) string += " $op" postfix.add(item) } // if // When we have our higher precedence // operators, deal with them. "*", "/" -> // If the stack is empty or the // top of the stack is a left // parentheses, we haven't seen // two operands so this operator // must be pushed on the stack. if (postfix.isEmpty() || postfix.last() == "(") postfix.add(item) // Otherwise, if we got a lower // precedence operator on the stack, // we need another operand so push // our new operator. else if (postfix.last() in listOf("+", "-")) postfix.add(item) // Otherwise, we got a higher // precedence operator on the stack // so pop it, add it to our result // string, and finish by pushing our // new operator. else { val op = postfix.removeAt(postfix.size-1) string += " $op" postfix.add(item) } // if // When we have a left parentheses, push // it on our stack. "(" -> postfix.add(item) // When we have a right parentheses, // while we haven't popped our left // parentheses, pop the top of our // stack, if it is the left parentheses, // exit our loop, otherwise, add the // operator into our result string. ")" -> while (true) { val op = postfix.removeAt(postfix.size-1) if (op == "(") break else string += " $op" } // while // Otherwise, when we have an operand, // put it into our result string. Note // we need a space to separate this // from any previous string. else -> if (string.isEmpty()) string = item else string += " $item" } // when } // for // While we have operators left on the stack, // pop the top one and add it to our result // string. while (postfix.isNotEmpty()) { val op = postfix.removeAt(postfix.size-1) string += " $op" } // while return string } // convert // Function to process the expression string. // Allocate an empty stack. fun process(string: String) { val stack = MutableList(0) { 0 } // Recursive function to handle carries, // borrows, and column simplifications // rexpressing a group values to be summed // until they reach one digit per column. // Parameters: offset is leading spacing // only needed to line up the output under // the dividend. format specifies the // spacing so all numbers display with // their digits in columns. terminator // is the line to place under the columns // of integers. elements is the list of // numbers that need simplifying. fun sum(offset: String, format: String, terminator: String, elements: MutableList>) { // Determine what type of processing // is required: nothing, carrying or // simplifying, and borrowing. We only // handle borrowing, when all values // have been completely simplified. // Default to nothing needs doing. // Allocate an array to check for // multiple digits in the column. // For each element in the list, for // each digit in the element, check it // out. var carry = false var borrow = 0 val digits = elements[0].size val sums = Array(digits) { 0 } for (element in elements) for (index in element.indices) // If we have seen a digit in this // column and we have one now, we // need to simplify. if (sums[index] != 0 && element[index] != 0) carry = true // Otherwise, if this digit is // negative, we must borrow so // remember this index and note // this column was used. else if (element[index] < 0) { borrow = index sums[index] += element[index] // Otherwise, note this column // was used. } else sums[index] += element[index] // If simplifying needed, do it. if (carry) { // Find the first column with a digit. // Allocate a place to hold the column. // For each possible column, for each // element in our list, if we find a // digit, save it's column and exit // our loops. var column = 0 outer@ for (index in 0 until digits) for (element in elements) if (element[index] != 0) { column = index break@outer } // if // Allocate a new empty list for our // values. For our ones column on up // to our highest, sum that column. val new = MutableList(0) { List(0) { 0 } } for (index in digits-1 downTo 0) { // For this column, we must get a // sum of all digits in it and a // list of what we added as a string. // Finally, we don't bother outputing // columns that had no digits. Default // the variables to not needed. For // each element in our lists, add it's // digit in. var subtotal = 0 var what = "(" var toss = true for (position in elements.indices) { // Get our digit. If it isn't zero, // this column is required. Add the // digit to our column total. // Finally, add our digit to the // string list (negative or first // digit doesn't need a leading // operation.) val value = elements[position][index] if (value != 0) toss = false subtotal += value what += (if (position == 0 || value < 0) "" else "+")+"$value" } // for // Finish off our string list. If // this column had digits, add them // to our new list and display it. what += ")" if (!toss) { new.add(subtotal.digits(digits)) println(offset+(if (index > column) " " else "+")+ (format.format(subtotal))+what) } // if } // for // We finished our new values so // display the line at the bottom. // Check for more needing to be done // by recursing. println(offset+terminator) sum(offset, format, terminator, new) // Otherwise, if we found a borrow to // handle, clone the existing elements, // add a borrow element, recurse with // the updated list. } else if (borrow > 0) { val new = MutableList(elements.size) { elements[it] } new.add(List(digits) { when (it) { borrow -> 10.pow(digits-it) borrow-1 -> -(10.pow(digits-it-1)) else -> 0 } }) sum(offset, format, terminator, new) } // if } // sum // Function to perform the first subtraction // simplification of a division before // letting our recursive sum handle the // rest. Parameters: offset is leading // spacing only needed to line up the output // under the dividend. format specifies the // spacing so all numbers display with // their digits in columns. terminator // is the line to place under the columns // of integers. elements is the list of // numbers that need simplifying. fun difference(offset: String, format: String, terminator: String, elements: MutableList>) { // Determine what type of processing // is required: nothing, and carrying or // simplifying. Default to nothing needs // doing. Allocate an array to check for // multiple digits in the column. // For each element in the list, for // each digit in the element, check it // out. var carry = false val digits = elements[0].size val sums = Array(digits) { 0 } for (element in elements) for (index in element.indices) // If we have seen a digit in this // column and we have one now, we // need to simplify. if (sums[index] != 0 && element[index] != 0) carry = true // Otherwise, note this column // was used. else sums[index] += element[index] // If simplifying needed, do it. if (carry) { // Find the first column with a digit. // Allocate a place to hold the column. // For each possible column, for each // element in our list, if we find a // digit, save it's column and exit // our loops. var column = 0 outer@ for (index in 0 until digits) for (element in elements) if (element[index] != 0) { column = index break@outer } // if // Allocate a new empty list for our // values. For our ones column on up // to our highest, sum that column. // The difference here is our first // number is our starting point and // the sum of the others are substracted // from it. val new = MutableList(0) { List(0) { 0 } } for (index in digits-1 downTo 0) { // For this column, we must get a // sum of all digits in it and a // list of what we added as a string. // Finally, we don't bother outputing // columns that had no digits. Default // the variables to not needed. For // each element in our lists, add it's // digit in. var subtotal = 0 var what = "(" var toss = true for (position in elements.indices) { // Get our digit. If it isn't zero, // this column is required. The // first digit is added to our // column total. The others digits // are subtracted from our column // total. Finally, add our digit to // the string list (first digit // doesn't need a leading operation.) val value = elements[position][index] if (value != 0) toss = false if (position == 0) { subtotal += value what += "$value" } else { subtotal -= value what += "-$value" } // if } // for // Finish off our string list. If // this column had digits, add them // to our new list and display it. what += ")" if (!toss) { new.add(subtotal.digits(digits)) println(offset+(if (index > column) " " else "+")+ (format.format(subtotal))+what) } // if } // for // We finished our new values so // display the line at the bottom. // Check for more needing to be done // by recursing with our sum. println(offset+terminator) sum(offset, format, terminator, new) } // if } // difference // Function to handle the top layer of an // addition before letting our recursive // sum handle the rest. fun add() { // If we don't have both operands, throw // an exception. if (stack.size < 2) throw IllegalStateException( "Addition missing operands!") // Get both operands, calculate our // answer, pop the top of the stack, // and replace the first operand with // our answer. val first = stack[stack.size-2] val second = stack[stack.size-1] val answer = first+second stack.removeAt(stack.size-1) stack[stack.size-1] = answer // Get our answers size and display our // equation. val size = answer.size() println(" %${size}d".format(first)) println("+%${size}d".format(second)) println("-".repeat(size+1)) // Find the size of our bigger number, // convert both numbers to digits, // allocate an empty list, and for // each of the digits, show the work. val digits = if (first > second) first.size() else second.size() val one = first.digits(digits) val two = second.digits(digits) val elements = MutableList(0) { List(0) { 0 } } for (index in 1..digits) { // Calculate this columns total, add // it to our list, and display our // work, when there was something // to add. val value = one[one.size-index]+ two[two.size-index] elements.add(value.digits(digits)) if (one[one.size-index] != 0 || two[two.size-index] != 0) println((if (index < digits) " " else "+")+ "%${size}d(%d+%d)".format( value, one[one.size-index], two[two.size-index])) } // for // Display the end of this calculation. // Call our recursive sum to see if more // are required. Once done display the // final answer. println("-".repeat(size+1)) sum("", "%${size}d", "-".repeat(size+1), elements) println(" %${size}d".format(answer)) println() } // add // Function to handle the top layer of an // subtraction before letting our recursive // sum handle the rest. fun subtract() { // If we don't have both operands, throw // an exception. if (stack.size < 2) throw IllegalStateException( "Subtraction missing operands!") // Get both operands, calculate our // answer, pop the top of the stack, // and replace the first operand with // our answer. val first = stack[stack.size-2] val second = stack[stack.size-1] val answer = first-second stack.removeAt(stack.size-1) stack[stack.size-1] = answer // If our second number is the biggest, // our calculation has a negative number // so throw an exception. if (first < second) throw IllegalStateException( "Bad subtraction $first-$second!") // Get our first number size, display our // equation, convert both numbers to // digits, allocate an empty list, and for // each of the digits, show the work. val size = first.size() println(" %${size}d".format(first)) println("-%${size}d".format(second)) println("-".repeat(size+1)) val one = first.digits(size) val two = second.digits(size) val elements = MutableList(0) { List(0) { 0 } } for (index in 1..size) { // Calculate this columns total, add // it to our list, and display our // work, when there was something // to add. val value = one[one.size-index]- two[two.size-index] elements.add(value.digits(size)) if (one[one.size-index] != 0 || two[two.size-index] != 0) println((if (index < size) " " else "+")+"%${size}d(%d-%d)".format( value, one[one.size-index], two[two.size-index])) } // for // Display the end of this calculation. // Call our recursive sum to see if more // are required. Once done display the // final answer. println("-".repeat(size+1)) sum("", "%${size}d", "-".repeat(size+1), elements) println(" %${size}d".format(answer)) println() } // subtract // Function to handle the top layer of an // multiplication before letting our // recursive sum handle the rest. fun multiply() { // If we don't have both operands, throw // an exception. if (stack.size < 2) throw IllegalStateException( "Multiplication missing operands!") // Get both operands, calculate our // answer, pop the top of the stack, // and replace the first operand with // our answer. val first = stack[stack.size-2] val second = stack[stack.size-1] val answer = first*second stack.removeAt(stack.size-1) stack[stack.size-1] = answer // Get our answers size and display our // equation, convert both numbers to // digits, allocate an empty list, for // each of the digits of our multiplier, // and for each of the digits of our // multiplicand, show the work. val size = answer.size() println(" %${size}d".format(first)) println("*%${size}d".format(second)) println("-".repeat(size+1)) val one = first.digits() val two = second.digits() val elements = MutableList(0) { List(0) { 0 } } for (double in 1..two.size) for (single in 1..one.size) { // Calculate these digits product, add // it to our list, and display our // work. val value = one[one.size-single]* two[two.size-double] elements.add(value.digits(size)) println((if (single < one.size || double < two.size) " " else "+")+ "%${size}d(%d*%d)".format(value, one[one.size-single], two[two.size-double])) } // for // Display the end of this calculation. // Call our recursive sum to see if more // are required. Once done display the // final answer. println("-".repeat(size+1)) sum("", "%${size}d", "-".repeat(size+1), elements) println(" %${size}d".format(answer)) println() } // multiply // Function to handle the top layer of an // division before letting our difference // and recursive sum handle the rest. fun divide() { // If we don't have both operands, throw // an exception. if (stack.size < 2) throw IllegalStateException( "Division missing operands!") // Get both operands, calculate our // answer & remainder, pop the top of // the stack, and replace the first // operand with our answer. val first = stack[stack.size-2] val second = stack[stack.size-1] val answer = first/second val remainder = first%second stack.removeAt(stack.size-1) stack[stack.size-1] = answer // Get our first number size, display our // equation, convert both numbers to // digits, make a mutable copy of our // dividend, and for each of the digits // of our answer, show the work. val size = first.size() print(" ".repeat(size+1)) print("%${size}d".format(answer)) if (remainder > 0) print("r$remainder") println() println(" ".repeat(size)+ "-".repeat(size+1)) println("%${size}d|%${size}d".format( second, first)) val one = second.digits() val two = answer.digits() var subtotal = first for (double in two.size downTo 1) { // Allocate an empty list and for // each of the digits of our divisor, // process the multiplication. val elements = MutableList(1) { subtotal.digits(size) } for (single in 1..one.size) { // Calculate these digits product, // subtract it from our running total, // add it to our list, and display our // work. val value = one[one.size-single]* two[two.size-double] subtotal -= value elements.add(value.digits(size)) println(" ".repeat(size)+ (if (single < one.size) " " else "-")+ "%${size}d(%d*%d)".format( value, one[one.size-single], two[two.size-double])) } // for // Display the end of this calculation. // Call our difference to see if more // are required. Once done display the // running total. println(" ".repeat(size)+ "-".repeat(size+1)) difference(" ".repeat(size), "%${size}d", "-".repeat(size+1), elements) println(" ".repeat(size+1)+ "%${size}d".format(subtotal)) } // for println() } // divide // Convert the line from infix to postfix // form and for each token in the line, // process the operation or push the integer // data onto the stack. for (element in convert(string).split(" ")) when (element) { "+" -> add() "-" -> subtract() "*" -> multiply() "/" -> divide() else -> stack.add(element.toInt()) } // when } // process // Main function to process this challenge. fun main(args: Array) { // Try reading the user's expressions. Count // how many were processed. Break out of // loop on end of file or empty line. // Process each line. If no lines got // processed, throw an exception to process // the default test case. try { var count = 0 while (true) { val string = readLine() ?: break if (string.isEmpty()) break process(string) count++ } // while if (count == 0) throw IllegalArgumentException( "Bad input!") // On no input lines exception, complain // and process the default test case. } catch (error: IllegalArgumentException) { println("Bad input using defaults!") process("(45*19+1)/19") // On an postfix state issue or other // runtime issue, abort with the error // message. } catch (error: Throwable) { println("Aborting: ${error.message}") } // try } // main

math ch