I want to write code in dart that can calculate like this expression: 100 * ( 2 12 ) / 14 (infix notation) taking into consideration the priority of operators. for ex: "*" is stronger than " ". The code below fixes my issue but it's written in JavaScript, I tried to convert it to dart but I am stuck.
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Infix Notation</title>
</head>
<body>
<script>
function evaluate(expression){
let tokens = expression.split(' ');
// Stack for numbers: 'values'
let values = [];
// Stack for Operators: 'ops'
let ops = [];
for (let i = 0; i < tokens.length; i ){
if (tokens[i] >= '0' && tokens[i] <= '9'){
let number = "";
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9'){
number = number tokens[i ];
}
document.write(number "</br>");
values.push(parseInt(number, 10));
// Right now the i points to
// the character next to the digit,
// since the for loop also increases
// the i, we would skip one
// token position; we need to
// decrease the value of i by 1 to
// correct the offset.
i--;
}
// Current token is an opening
// brace, push it to 'ops'
else if (tokens[i] == '(')
{
ops.push(tokens[i]);
}
// Closing brace encountered,
// solve entire brace
else if (tokens[i] == ')')
{
while (ops[ops.length - 1] != '(')
{
values.push(applyOp(ops.pop(),
values.pop(),
values.pop()));
}
ops.pop();
}
// Current token is an operator.
else if (tokens[i] == ' ' ||
tokens[i] == '-' ||
tokens[i] == '*' ||
tokens[i] == '/')
{
// While top of 'ops' has same
// or greater precedence to current
// token, which is an operator.
// Apply operator on top of 'ops'
// to top two elements in values stack
while (ops.length > 0 &&
hasPrecedence(tokens[i],
ops[ops.length - 1]))
{
values.push(applyOp(ops.pop(),
values.pop(),
values.pop()));
}
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been
// parsed at this point, apply remaining
// ops to remaining values
while (ops.length > 0){
values.push(applyOp(ops.pop(),
values.pop(),
values.pop()));
}
// Top of 'values' contains
// result, return it
return values.pop();
}
// Returns true if 'op2' has
// higher or same precedence as 'op1',
// otherwise returns false.
function hasPrecedence(op1, op2){
if (op2 == '(' || op2 == ')')
{
return false;
}
if ((op1 == '*' || op1 == '/') &&
(op2 == ' ' || op2 == '-'))
{
return false;
}
else
{
return true;
}
}
// A utility method to apply an
// operator 'op' on operands 'a'
// and 'b'. Return the result.
function applyOp(op, b, a){
switch (op)
{
case ' ':
return a b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
{
document.write("Cannot divide by zero");
}
return parseInt(a / b, 10);
}
return 0;
}
document.write(evaluate("10,5 2 * 6") "</br>");
document.write(evaluate("100 * 2 12") "</br>");
document.write(evaluate("100 * ( 2 12 )") "</br>");
document.write(evaluate( "100 * ( 2 12 ) / 14") "</br>");
// This code is contributed by decode2207.
</script>
</body>
</html>
In dart there is no built in function for stack so we have to write its class in order to use push(), pop(), length.. as below:
class Values<T> {
final _list = <T>[];
void push(T value) => _list.add(value);
T pop() => _list.removeLast();
T get top => _list.last;
bool get isEmpty => _list.isEmpty;
bool get isNotEmpty => _list.isNotEmpty;
int get length => _list.length;
T get peek => _list.last;
@override
String toString() => _list.toString();
}
CodePudding user response：
1. Closest translation to Dart with some refactoring (personal advice: don't use this past simple use cases, like the ones in the examples above)
num evaluate(String expression) {
var tokens = expression.split(' ');
// Stack for numbers: 'values'
List<num> values = [];
// Stack for Operators: 'ops'
List<String> ops = [];
for (var i = 0; i < tokens.length; i ) {
if (num.tryParse(tokens[i]) != null) {
// dart reafctor: removed the while loop here as it is not needed and bad
values.add(num.parse(tokens[i]));
}
// Current token is an opening
// brace, push it to 'ops'
else if (tokens[i] == '(') {
ops.add(tokens[i]);
}
// Closing brace encountered,
// solve entire brace
else if (tokens[i] == ')') {
while (ops.last != '(') {
values.add(applyOp(
ops.removeLast(), values.removeLast(), values.removeLast()));
}
ops.removeLast();
}
// Current token is an operator.
else if (tokens[i] == ' ' ||
tokens[i] == '-' ||
tokens[i] == '*' ||
tokens[i] == '/') {
// While top of 'ops' has same
// or greater precedence to current
// token, which is an operator.
// Apply operator on top of 'ops'
// to top two elements in values stack
while (ops.isNotEmpty && hasPrecedence(tokens[i], ops.last)) {
values.add(applyOp(
ops.removeLast(), values.removeLast(), values.removeLast()));
}
// Push current token to 'ops'.
ops.add(tokens[i]);
}
}
// Entire expression has been
// parsed at this point, apply remaining
// ops to remaining values
while (ops.isNotEmpty) {
values.add(
applyOp(ops.removeLast(), values.removeLast(), values.removeLast()));
}
// Top of 'values' contains
// result, return it
return values.removeLast();
}
bool hasPrecedence(String op1, String op2) {
if (op2 == '(' || op2 == ')') {
return false;
}
if ((op1 == '*' || op1 == '/') && (op2 == ' ' || op2 == '-')) {
return false;
} else {
return true;
}
}
num applyOp(String op, num b, num a) {
switch (op) {
case ' ':
return a b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0) {
throw "Cannot divide by zero";
}
return a / b;
}
return 0;
}
Test cases
void main() {
print(evaluate("100 * 2 12")); // 212
print(evaluate("100 * ( 2 12 )")); // 1400
print(evaluate( "100 * ( 2 12 ) / 14")); // 100
}
2. This evaluates an arithmetic expression by using Regular expression matches. So not a direct translation of your code, but will work nonetheless.
num evaluate(String expr) {
var divAndMult =
RegExp(r"\(?\s*(\d (?:\.\d*)?)\s*([/*])\s*(\d (?:\.\d*)?)\s*\)?");
var addAndSub =
RegExp(r"\(?\s*(\d (?:\.\d*)?)\s*([ -])\s*(\d (?:\.\d*)?)\s*\)?");
var nextInput = expr;
while (divAndMult.hasMatch(nextInput) || addAndSub.hasMatch(nextInput)) {
nextInput = nextInput.replaceAllMapped(divAndMult, (match) {
if (match[2] == "*") {
return (num.parse(match[1]!) * num.parse(match[3]!)).toString();
}
return (num.parse(match[1]!) / num.parse(match[3]!)).toString();
}).replaceAllMapped(addAndSub, (match) {
if (match[2] == " ") {
return (num.parse(match[1]!) num.parse(match[3]!)).toString();
}
return (num.parse(match[1]!) - num.parse(match[3]!)).toString();
});
}
return num.parse(nextInput);
}
This can be refactored to ease adding new operators, like so:
extension ApplyOp on Match {
String applyOp(num Function(num a, num b) op) {
return op(num.parse(this[1]!), num.parse(this[3]!)).toString();
}
}
num evaluate(String expr) {
var divMultAndModulo =
RegExp(r"\(?\s*(\d (?:\.\d*)?)\s*([/*%])\s*(\d (?:\.\d*)?)\s*\)?");
var addAndSub =
RegExp(r"\(?\s*(\d (?:\.\d*)?)\s*([ -])\s*(\d (?:\.\d*)?)\s*\)?");
var nextInput = expr;
while (divMultAndModulo.hasMatch(nextInput) || addAndSub.hasMatch(nextInput)) {
nextInput = nextInput.replaceAllMapped(divMultAndModulo, (match) {
if (match[2] == "*") {
return match.applyOp((a, b) => a * b);
}
if(match[2] == '%') {
return match.applyOp((a, b) => a % b);
}
return match.applyOp((a, b) => a / b);
}).replaceAllMapped(addAndSub, (match) {
if (match[2] == " ") {
return match.applyOp((a, b) => a b);
}
return match.applyOp((a, b) => a - b);
});
}
return num.parse(nextInput);
}
Test cases
void main() {
print(evaluate("(8 * 8) - (20 / 5) 8")); // 68
print(evaluate("( 2 12 )")); // 14
print(evaluate("100 * ( 2 12 ) / 14")); // 100
print(evaluate("10.5 2 * 6")); // 22.5
print(evaluate("20 % 3")); // 2
}