Taschenrechner

[Zel2491]

Hallo allerseits

Ich bin dabei einen Taschenrechner zu programmieren... einen recht simplen, wird dann noch erweitert - vorerst kann dieser nur + - * / % und das bisher auch nur mit 2 Zahlen in einer Anweisung, z.B. 7*5 erkennt er. Jetzt will ich aber, dass der Rechner auch 7*5+3 rechnen kann. Ich wollte die Eingabe über ein Array machen, bin mir aber nicht ganz sicher, wie das zu realisieren ist...

cin >> iZahlen[0] >> cOperator >> iZahlen[1];

die erste Zahl wird an die 1. Stelle des Arrays geschrieben, der Operator muss auch in ein Array oder?

cin >> iZahlen[0] >> iZahlen[1]>> iZahlen[2];

oder?

Nur hab ich jetzt 2, nein 3 Fragen dazu:

1. Frage: ist die Idee richtig, oder befinde ich mich auf dem Holzweg?
2. Frage: selbst das klappt nur mit 2 Zahlen... ich müsste ja theoretisch die Eingabe 7*5*3+2-1 ermöglichen... ich kann ja aber nicht vorher wissen, was der Benutzer eingeben wird... ich hoffe, ihr versteht meine Frage...^^
3. Frage: wie überprüfe ich dann, ob in einem Array eine Zahl, oder ein Rechenoperant vorhanden ist...?

Gruß Zel

[C++ Forumbot]

Dieser Thread wurde von Moderator/in Martin Richter aus dem Forum MFC (Visual C++) in das Forum C++ (auch C++0x und C++11) verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[Werner_logoff]

Zel2491 schrieb:

2. Frage: selbst das klappt nur mit 2 Zahlen... ich müsste ja theoretisch die Eingabe 7*5*3+2-1 ermöglichen... ich kann ja aber nicht vorher wissen, was der Benutzer eingeben wird... ich hoffe, ihr versteht meine Frage...^^

Hallo Zel,

schaue Dir mal diesen Ausdrucksparser an und den theoretischen Unterbau und dieser Thread über Taschenrechner ist vielleicht auch interessant.

[seldon]

Ein Recdesc-Parser scheint mir dafür eigentlich Overkill. Ich hab hier noch eine Implementation des Shunting-Yard-Algorithmus herumliegen, die Grundrechenarten, Potenz und unäre Operatoren mit zwei Stacks erschlägt:

#include <boost/variant.hpp>

#include <cmath>
#include <iostream>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>

namespace syard {
  namespace impl {
    template<typename T> T top_and_pop(std::stack<T> &s) {
      if(s.empty()) throw std::invalid_argument("Invalid expression");

      T ret = s.top();
      s.pop();
      return ret;
    }

    typedef std::stack<double> num_stack_t;
    void no_real_calculation_function(num_stack_t &) { throw std::runtime_error("This should not happen."); }

    class operator_description {
    public:
      typedef void (*function_t)(num_stack_t &);

      operator_description(int        priority          = -1,
                           function_t func              = no_real_calculation_function,
                           bool       left_associative  = true)
        : priority_        (priority),
          func_            (func),
          left_associative_(left_associative)
        { }

      int  priority        () const { return priority_        ; }
      bool left_associative() const { return left_associative_; }

      void apply(std::stack<double> &num_stack) const { func_(num_stack); }

    private:
      int        priority_;
      function_t func_;
      bool       left_associative_;
    };

    template<typename func_t> void numstack_apply_binary(num_stack_t &num_stack, func_t const &func) {
      double y = top_and_pop(num_stack);
      double x = top_and_pop(num_stack);
      num_stack.push(func(x, y));
    }

    double add     (double x, double y) { return x + y; }
    double subtract(double x, double y) { return x - y; }
    double multiply(double x, double y) { return x * y; }
    double divide  (double x, double y) { return x / y; }

    void numstack_add     (num_stack_t &num_stack) { numstack_apply_binary(num_stack, add     ); }
    void numstack_subtract(num_stack_t &num_stack) { numstack_apply_binary(num_stack, subtract); }
    void numstack_multiply(num_stack_t &num_stack) { numstack_apply_binary(num_stack, multiply); }
    void numstack_divide  (num_stack_t &num_stack) { numstack_apply_binary(num_stack, divide  ); }
    void numstack_power   (num_stack_t &num_stack) { numstack_apply_binary(num_stack, static_cast<double(*)(double, double)>(std::pow)); }
    void numstack_noop    (num_stack_t &         ) { }
    void numstack_negate  (num_stack_t &num_stack) { num_stack.push(-top_and_pop(num_stack)); }

    enum operator_id {
      binary_plus,
      binary_minus,
      binary_mult,
      binary_div,
      binary_pow,
      unary_plus,
      unary_minus,
      paren_open,
      paren_close,
      operator_id_count
    };

    operator_description const op_descriptions[operator_id_count] = {
      operator_description(0, numstack_add     ),
      operator_description(0, numstack_subtract),
      operator_description(1, numstack_multiply),
      operator_description(1, numstack_divide  ),
      operator_description(2, numstack_power , false),
      operator_description(2, numstack_noop  , false),
      operator_description(2, numstack_negate, false)
    };

    operator_id lookup_op_id(char op, bool prefer_unary) {
      switch(op) {
      case '+': return prefer_unary ? unary_plus  : binary_plus ;
      case '-': return prefer_unary ? unary_minus : binary_minus;
      case '*': return binary_mult;
      case '/': return binary_div;
      case '^': return binary_pow;
      case '(': return paren_open;
      case ')': return paren_close;
      }

      throw std::invalid_argument(std::string("Unknown operator: ") + op);
    }

    class calculation_state : public boost::static_visitor<> {
    public:
      void operator()(double x) { num_stack_.push(x); }
      void operator()(operator_id op) {
        if(op == paren_open) {
          op_stack_.push(op);
        } else if(op == paren_close) {
          // Lazy-Evaluation, damit op_stack.top() nicht bei leerem Stack
          // ausgeführt wird. Das funktioniert, weil perform_top_operation bei
          // leerem op_stack eine Exception schmeißt.
          while(op_stack_.empty() || op_stack_.top() != paren_open) {
            perform_top_operation();
          }

          op_stack_.pop();
        } else {
          operator_description const &op_desc = op_descriptions[op];

          while(!op_stack_.empty() &&
                ((op_desc.left_associative()
                  && op_desc.priority() <= op_descriptions[op_stack_.top()].priority())
                 || (op_desc.priority() <  op_descriptions[op_stack_.top()].priority()))) {
            perform_top_operation();
          }

          op_stack_.push(op);
        }
      }

      void finalize() {
        // num_stack.empty() ist nur true, wenn ein leerer
        // Ausdruck bzw. (), (()) etc. angegeben wurde -
        // perform_top_operation schmeißt dann einen Fehler (s.o.)
        while(!op_stack_.empty() || num_stack_.empty()) {
          perform_top_operation();
        }
      }

      double result() {
        finalize();
        return num_stack_.top();
      }

    private:
      void perform_top_operation() { op_descriptions[top_and_pop(op_stack_)].apply(num_stack_); }

      std::stack<double>     num_stack_;
      std::stack<operator_id> op_stack_;
    };

    typedef boost::variant<double, operator_id> token_t;

    std::istream &read_token(std::istream &in, token_t &dest, operator_id &lastop) {
      double x;
      char c;

      if(in >> c) {
        if((c >= '0' && c <= '9') || c == '.') {
          in.unget();
          if(in >> x) {
            dest = x;
            lastop = paren_close;
          }
        } else {
          operator_id opid = lookup_op_id(c, lastop != paren_close);
          dest   = opid;
          lastop = opid;
        }
      }

      return in;
    }
  }

  double calculate(std::string const &expr) {
    std::istringstream parser(expr);
    impl::token_t token;
    impl::calculation_state state;
    impl::operator_id lastop = impl::unary_plus;

    while(impl::read_token(parser, token, lastop)) {
      boost::apply_visitor(state, token);
    }

    return state.result();
  }
}

int main(int argc, char *argv[]) {
  std::string expr;

  if(argc > 1) {
    expr = argv[1];
  } else {
    std::getline(std::cin, expr);
  }

  std::cout << syard::calculate(expr) << std::endl;
}

[314159265358979]

#include <iostream>
#include <string>
#include <stdexcept>
#include <cctype>
#include <map>
#include <cstdlib>
#include <cmath>

struct parse_error : std::runtime_error
{
	parse_error(std::string const& what)
		: runtime_error(what)
	{}
};

typedef double calculation_type;

std::map<std::string, calculation_type> constants;
std::map<std::string, calculation_type (*) (calculation_type)> functions;

// identifier    = {A-Za-z_} {A-Za-z0-9_}*
// function-call = identifier [factor]
// factor        = ['+' | '-'] (double | function-call | '(' sum ')')
// product       = factor  [('*' | '/') factor ]*
// sum           = product [('+' | '-') product]*

calculation_type parse_sum(char const*& input);
calculation_type parse_factor(char const*& input);

void skip_spaces(char const*& input)
{
	while(std::isspace(*input))
		++input;
}

double parse_double(char const*& input)
{
	return std::strtod(input, const_cast<char**>(&input));
}

std::string parse_identifier(char const*& input)
{
	skip_spaces(input);
	std::string identifier(1, *input++);

	while(std::isalnum(*input) || *input == '_')
		identifier += *input++;

	return identifier;
}

calculation_type parse_function_call(char const*& input)
{
	skip_spaces(input);

	std::string const name = parse_identifier(input);

	{
		auto const iter = constants.find(name);

		if(iter != constants.end())
			return iter->second;
	}

	{
		auto const iter = functions.find(name);

		if(iter != functions.end())
		{
			skip_spaces(input);
			calculation_type const argument = parse_factor(input);
			return iter->second(argument);
		}
	}

	throw parse_error("unknown function '" + name + "'");
}

calculation_type parse_factor(char const*& input)
{
	skip_spaces(input);

	if(*input == '+')
		return parse_factor(++input);

	if(*input == '-')
		return -parse_factor(++input);

	if(std::isdigit(*input) || *input == '.')
		return parse_double(input);

	if(std::isalpha(*input) || *input == '_')
		return parse_function_call(input);

	if(*input == '(')
	{
		skip_spaces(input);
		calculation_type const value = parse_sum(++input);

		skip_spaces(input);
		if(*input != ')')
			throw parse_error("closing brace ')' missing");

		++input;
		return value;
	}

	throw parse_error("expected value here: " + std::string(input));
}

calculation_type parse_product(char const*& input)
{
	skip_spaces(input);
	calculation_type product = parse_factor(input);

	skip_spaces(input);
	while(*input == '*' || *input == '/')
		if(*input == '*')
			product *= parse_factor(++input);
		else if(*input == '/')
			product /= parse_factor(++input);

	return product;
}

calculation_type parse_sum(char const*& input)
{
	skip_spaces(input);
	calculation_type sum = parse_product(input);

	skip_spaces(input);
	while(*input == '+' || *input == '-')
		if(*input == '+')
			sum += parse_product(++input);
		else if(*input == '-')
			sum -= parse_product(++input);

	return sum;
}

calculation_type eval(char const* input)
{
	return parse_sum(input);
}

int main()
{
	char const* const input = "sin (pi / 2) - cos 0";

	constants["pi"] = 3.14159265;
	constants["e"]  = 2.71828183;

	functions["sin"] = std::sin;
	functions["cos"] = std::cos;

	try
	{
		std::cout << eval(input);
	}

	catch(parse_error const& e)
	{
		std::cout << "parse error: " << e.what();
	}

	std::cin.get();
}

Da ist mein Recursive-Descent Parser wohl kürzer.
http://ideone.com/4ZTRR :p
Aber wahrscheinlich ist das alles nicht das, was der TE will.

[seldon]

Naja, der Vergleich hakt durch die unterschiedlichen Features ein bisschen. Ich kann keine Funktionsaufrufe und Konstanten, du kannst keine Potenz (rechtsassoziativ!) und keine unären Operatoren. Ich würde allerdings behaupten, dass die grundlegende Funktionsweise des Shunting-Yard-Algorithmus einfacher ist als die eines Recdesc-Parsers -- insbesondere, wenn dieser LL(1) ist.

Um Funktionsaufrufe damit zu erschlagen, bräuchte ich aber wohl einen Lexer. Die Zerlegung in Tokens ist schon mit unären Operatoren eine etwas haarige Angelegenheit.

[314159265358979]

Natürlich hab ich unäre Operatoren, sieh dir die Grammatik an. Und Potenzen sind ja jetzt wirklich nicht besonders schwer einzubauen.

[seldon]

Ah, dein Code entspricht der Beschreibung im Kommentar nicht (mit der ginge bspw. +-+2 nicht). Im Code dagegen setzt du

factor = ([+ | -] factor) | double | function_call | ('(' sum ')')

um, womit es funktioniert. So genau hatte ich jetzt nicht hingesehen. Potenz ist insofern etwas spannender, als dass die rechtsassoziativ ist (2³4 = 2⁽³4)). Machbar ist das auch, aber du kannst nicht einfach die parse_product-Funktion nehmen und einen anderen Operator reinpasten.

[314159265358979]

Ah, danke für den Hinweis. Aber dass Potenzen rechtsassoziativ sind, weiß ich doch. <.<
Mal abgesehen davon hat ^ ein höhere Priorität, muss also sowieso zuerst drankommen.

[314159265358979]

Done.
http://ideone.com/S272N