How to Rearrange a String Equation

How to rearrange a string equation?

I started with a Syntax Diagram to define (I wouldn't call it) a language:

Syntax Diagram

Then I translated this into a hand-written parser.

parse-equation.cc:

#include <iostream>
#include <algorithm>

int parseDigit(const char *&la)
{
  switch (*la) {
    case '0': ++la; return 0;
    case '1': ++la; return 1;
    case '2': ++la; return 2;
    case '3': ++la; return 3;
    case '4': ++la; return 4;
    case '5': ++la; return 5;
    case '6': ++la; return 6;
    case '7': ++la; return 7;
    case '8': ++la; return 8;
    case '9': ++la; return 9;
    default: return -1; // ERROR!
  }
}

int parseNumber(const char *&la)
{
  int value = parseDigit(la);
  if (value < 0) return -1; // ERROR!
  for (;;) {
    const int digit = parseDigit(la);
    if (digit < 0) return value;
    value *= 10; value += digit;
  }
}

struct Term {
  int coeff; // -1 ... missing
  int expon; // -1 ... missing -> ERROR

  Term(int coeff = -1, int expon = 0): coeff(coeff), expon(expon) { }
};

Term parseTerm(const char *&la)
{
  Term term;
  term.coeff = parseNumber(la);
  if (*la == 'x') {
    ++la;
    term.expon = parseDigit(la);
    if (term.coeff < 0) term.coeff = 1; // tolerate missing coeff. for x
  }
  return term;
}

struct Expression {
  bool error;
  int coeffs[10];

  Expression(bool error = false): error(error)
  {
    std::fill(std::begin(coeffs), std::end(coeffs), 0);
  }
};

Expression parseExpression(const char *&la)
{
  Expression expr;
  int sign = +1;
  do {
    const Term term = parseTerm(la);
    if (term.expon < 0) return Expression(true); // ERROR!
    expr.coeffs[term.expon] += sign * term.coeff;
    switch (*la) {
      case '+': sign = +1; ++la; break;
      case '-': sign = -1; ++la; break;
      case '=': break;
      default: return Expression(true); // ERROR!
    }
  } while (*la != '=');
  ++la;
  // parse right hand side
  const int result = parseNumber(la);
  if (result < 0) return Expression(true); // ERROR!
  expr.coeffs[0] -= result;
  // check for extra chars
  switch (*la) {
    case '\n': ++la;
    case '\0': break;
    default: return Expression(true); // ERROR!
  }
  return expr;
}

std::ostream& operator<<(std::ostream &out, const Expression &expr)
{
  if (expr.error) out << "ERROR!";
  else {
    bool empty = true;
    for (size_t i = 9; i; --i) {
      const int coeff = expr.coeffs[i];
      if (coeff) out << coeff << 'x' << i << std::showpos, empty = false;
    }
    if (empty) out << 0;
    out << std::noshowpos << '=' << -expr.coeffs[0];
  }
  return out;
}

int main()
{
  const char *samples[] = {
    "2x1+3x2+4x3=16",
    "1x1+2x2+1x3=8",
    "3x1+1x2+2x3=13",
    "2x1+3x2+5+4x3-11=10",
    "x1+3x2-x3=10"
  };
  enum { nSamples = sizeof samples / sizeof *samples };
  for (size_t i = 0; i < nSamples; ++i) {
    std::cout << "Parse '" << samples[i] << "'\n";
    const char *la = samples[i];
    std::cout << "Got    " << parseExpression(la) << std::endl;
  }
  return 0;
}

Compiled with g++ and tested in cygwin:

$ g++ -std=c++11 -o parse-equation parse-equation.cc 

$ ./parse-equation
Parse '2x1+3x2+4x3=16'
Got    4x3+3x2+2x1=16
Parse '1x1+2x2+1x3=8'
Got    1x3+2x2+1x1=8
Parse '3x1+1x2+2x3=13'
Got    2x3+1x2+3x1=13
Parse '2x1+3x2+5+4x3-11=10'
Got    4x3+3x2+2x1=16
Parse 'x1+3x2-x3=10'
Got    -1x3+3x2+1x1=10

$

Life Demo on Coliru

Note:

  1. Instead of parseDigit() and parseNumber(), std::strtol() could be used. This would reduce the code significantly.

  2. I used const char* for the "read head" la (... abbr. for "look ahead"). The pure C++ way might have been a std::stringstream or a std::string::iterator but, may be, I'm not used enough to these new fancy things. For me, the const char* was the most intuitive way...

  3. The result on right hand side is simply subtracted from the coefficient for x0. So, either the right hand side is 0, or the negative coefficient for x0 becomes right hand side. For my pretty-printing operator<<(), I chose the latter option.

  4. The error handling is rather poor and could be enhanced with more detailed infos about the reason of failed parsing. I left this out to not to "blow" the code even more.

  5. The parser could be enhanced easily to skip white space at any appropriate place. This would improve the convenience.

  6. In the current state, the result on right hand side might not be a negative number. I leave this extension as exercise.

Rearrange a string in R Studio

Something like this?

> paste(rev(strsplit(a," ")[[1]]),collapse=" ")
[1] "day good"

split, rearrange and join string in dataframe

As per my understanding your rearrange function should be like this:

def rearrange(x):
        return " -> ".join(x.split("->")[::-1])

because, you are using it to apply and not directly manipulating data.

Java String reorder

One way would be regex. This probably isn't the most efficient way but it's fairly clean:

public static void main(String args[]) {
    final Pattern pattern = Pattern.compile("(\\d++)\\.([^,]++),\\s*+([^,]++),\\s*+(.*+)");
    final Matcher matcher = pattern.matcher("");
    //for each input string
    final String input = "Subject, Uni Name, Location 2";
    matcher.reset(input);
    final String output = matcher.replaceAll("$1, $3, $2, $4");
    System.out.println(output);
}

So you pre-compile your Pattern and reuse the Matcher for maximum speed. You then simply do a replaceAll on each input String.

Python/Pandas - Rearrange string from column value

You may use strftime

df['new_Quarter'] = df.Quarter.dt.strftime('Q%q %y')

As a side note, the column Quarter can also be simply created using to_period 

df['Quarter'] = df.Date.dt.to_period('Q')
        Date Quarter new_Quarter
0 2019-09-18  2019Q3       Q3 19
1 2019-03-18  2019Q1       Q1 19
2 2019-05-13  2019Q2       Q2 19

Algorithm(s) for rearranging simple symbolic algebraic expressions

What you want is equation solving algorithm(s). But i bet that this is huge topic. In general case, there may be:

  • system of equations
  • equations may be non-linear, thus additional algorithms such as equation factorization needed.
  • knowledge how to reverse functions is needed,- for example =>
    sin(x) + 10 = z, solving for x we reverse sin(), which is arcsin(). (Not all functions may be reversible !)
  • finally some equations may be hard-solvable even for CAS, such as
    sin(x)+x=y, solve for x.

Hard answer is - your best bet is to take source code of some CAS,- for example you can take a look at MAXIMA CAS source code which is written in LISP. And find code which is responsible for equation solving.

Easy answer - if all that you need is solving equation which is linear and is composed only from basic operators +-*/. Then you know answer already - use old good paper method
- think of what rules we used on paper, and just re-write these rules as symbolic algorithm which manipulates equation string.

good luck !

How to rearrange a complicated equation by Python

The equation you are trying to solve is:

In [23]: eq                                                                                                                       
Out[23]: 
      ⎛           -n⎞               
    C⋅⎝1 - (r + 1)  ⎠             -n
P = ───────────────── + fv⋅(r + 1)  
            r

We can rearrange this into a polynomial like so

In [24]: eq2 = Eq(eq.lhs * (1+r)**n * r, eq.rhs * (1+r)**n * r).expand()                                                          

In [25]: eq2                                                                                                                      
Out[25]: 
           n            n           
P⋅r⋅(r + 1)  = C⋅(r + 1)  - C + fv⋅r

Now we see that this is a polynomial except that the exponent n is symbolic. In general this kind of equation will not have a solution expressible in closed form - that is why sympy has no algorithms for this particular case (it is not a limitation of sympy itself).

It is possible to solve this equation numerically but numerical solution only works if we have numerical values for each of the parameters. If we substitute numbers for the parameters then nsolve can find the solution numerically:

In [26]: eq3 = eq.subs({P:1, C:2, fv:1, n:100})                                                                                   

In [27]: eq3                                                                                                                      
Out[27]: 
                   ⎛        1     ⎞
                 2⋅⎜1 - ──────────⎟
                   ⎜           100⎟
        1          ⎝    (r + 1)   ⎠
1 = ────────── + ──────────────────
           100           r         
    (r + 1)                        

In [28]: nsolve(eq3, r, 1)                                                                                                        
Out[28]: 2.00000000000000

But note that the solutions to this equation are not unique for example -2 is also a solution here:

In [52]: nsolve(eq3, r, -1.9)                                                                                                     
Out[52]: -2.00000000000000

This particular equation has something like 100 roots although not necessarily all real.


Related Topics

What Does a A() Mean

Logical Xor Operator in C++

Has the New C++11 Member Initialization Feature at Declaration Made Initialization Lists Obsolete

What Is the Meaning of Clang's -Wweak-Vtables

How to Create My Own Ostream/Streambuf

Custom Manipulator for C++ iOStream

Linking Libraries in Xcode

C++ How to Generate All the Permutations of Function Overloads

Dark Transparent Layer Over a Qmainwindow in Qt

Are There Stackless or Heapless Implementation of C++

Why Do I Get _Crtisvalidheappointer(Block) And/Or Is_Block_Type_Valid(Header->_Block_Use) Assertions

How to Convert a Char Array to a String

Generate Sha Hash in C++ Using Openssl Library

Virtual Inheritance

Compiling External C++ Library for Use with iOS Project

What Happens If I Read a Map's Value Where the Key Does Not Exist

Empirically Determine Value Category of C++11 Expression

Complete C++ I18N Gettext() "Hello World" Example


Leave a reply



Submit