SenselessCoder - 1 year ago
540 0

No description

C

# AASDASD

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_EXPRESSION_SIZE 11 + 1
#define MAX_VARIABLES 9

int zero_nine[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int one_nine[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

struct variable {
int coefficient;
int* ptr;
int side;
int* value_set;
unsigned value_count;
};

typedef struct variable Variable;

struct equation {
Variable* variables[9]; // max
unsigned var_count;
};

typedef struct equation Equation;

int int_pow(int n, int k) {
int res = 1;
for(int i = 0; i < k; ++i)
res *= n;
return res;
}

void AddVariable(Equation* E, Variable* V) {
E->variables[E->var_count++] = V;
}

int IsImpossible(char* expression) {
// if all letters are same or end letters are same, no solution
if(
(expression[0] == expression[4] && expression[0] == expression[8]) ||
(!strncmp(expression, expression + 4, 3) && !strncmp(expression, expression + 8, 3))
)
return 1;
return 0;
}

char* evaluate(char* expression) {
char* res;

// check for impossible cases first
if(IsImpossible(expression)) {
res	= (char *) malloc(sizeof(char) * strlen("No Solution!"));
strcpy(res, "No Solution!");
return res;
}
res = (char *) malloc(sizeof(char) * MAX_EXPRESSION_SIZE);
// now try to find solutions, first describe the given characters as equations
Equation E;
E.var_count = 0;
int a = -1, b = -1, c = -1, d = -1, e = -1, f = -1, g = -1, h = -1, i = -1;
int* max_variables[MAX_VARIABLES] = { &a, &b, &c, &d, &e, &f, &g, &h, &i };
int side_mode = 0, powcounter = 0;
for(int j = 0; j < MAX_EXPRESSION_SIZE; ++j) {
if(expression[j] == '+')
continue;
if(expression[j] == '=') {
side_mode = 1;
continue;
}
Variable* V = (Variable *) malloc(sizeof(Variable));
// we know we always get 3 digit numbers but we can easily change if we need to
V->coefficient = int_pow(10, 2 - (powcounter % 3));
V->ptr = max_variables[expression[j] - 'A'];
V->side = side_mode;
if(!(powcounter % 3)) { // beginning of a number
V->value_count = 9;
V->value_set = one_nine;
}
else {
V->value_count = 10;
V->value_set = zero_nine;
}
++powcounter;
}
--E.var_count; // we counted 1 too many in add function
for(int j = 0; j < E.var_count; ++j)
printf("%d %c %d\n", E.variables[j]->coefficient, 'A' + (E.variables[j]->ptr - max_variables[0]), E.variables[j]->side);
// we got a representaion of the equation, now try to solve it
int solved = 0;
// O(N), where N is number of distinct variables. All of them have a constant x9 multiplier.
// An optimization we can do is, we first assign possible max values to rhs number, then go down. We need max number.
do {
// try to assign values to all variables and try if it solves the equation
for(int j = E.var_count; j >= 0; --j) {
// first assign rhs numbers (check if assigned by using -1 equality, reset to -1 after computation)
for(int k = E.variables[j]->value_count; k >= 0; --k) {
if(*(E.variables[j]->ptr) != -1) // can be set before due to same variable cases
*(E.variables[j]->ptr) = E.variables[j]->value_set[k];
}
}
} while(!solved);
return res;
}

int main() {
char expression[MAX_EXPRESSION_SIZE] = { 0 };
do {
printf("Enter the formula: ");
scanf("%s", expression);
char* res = evaluate(expression);
printf("%s\n", res);
free(res);
} while(expression[0] != '-');
return 0;
}``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download