Блог пользователя aakarshmadhavan

Автор aakarshmadhavan, история, 6 лет назад, По-английски

I feel really very stupid right now.

I am stuck on this problem and it sounding very very easy. I know it has to do with stack but the stupid multiplication and division are making it hard for me.

What can I do?

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Assuming all whitespace has been removed:

solve(l, r):
	for(i in [l, r)):
		if s[i] == '+' or s[i] == '-': return solve(left, i) `s[i]` solve(i + 1, right)
        for(i in [l, r)):
		if s[i] == '*' or s[i] == '/': return solve(left, i) `s[i]` solve(i + 1, right)
	return integer representation of s[l ... r - 1]

ans = solve(0, n)

This can be easily optimized further.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    Thanks, but I am really struggling with this problem because of multiplication and division mixed with add/sub. Can you help me here?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      The Shunting-yard algorithm should work. What about the mult/div are you having trouble with?

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

i think this could work

you have 2 stack: operatorStack and digitStack

scan all char in string

  • if digit, push it to digitStack

  • if operator and it has not less precedence than operator on top of operatorStack, push it to operatorStack

idea is whenever you have '*' or '/' on top of stack and the next operation is '+' or '-', you have to calculate the expression until top of stack is '+' or '-' (because you have to calculate all '*' and '/' before going to next operation), then push the result of calculation to digitStack

result will be calculation of operator and digit left on the stack after scan the string

sorry for my bad english

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think you need to look on process_stack function

#include <iostream>
#include <map>
#include <stack>

using namespace std;
typedef long long number_t;
typedef unsigned priority_t;

number_t add(const number_t &lhs, const number_t &rhs) {
    return lhs + rhs;
}

number_t sub(const number_t &lhs, const number_t &rhs) {
    return lhs - rhs;
}

number_t mul(const number_t &lhs, const number_t &rhs) {
    return lhs * rhs;
}

number_t div(const number_t &lhs, const number_t &rhs) {
    return lhs / rhs;
}

map<char, priority_t> priority_map = {
    {'*', 2},
    {'/', 2},
    {'+', 1},
    {'-', 1}
};

map<char, number_t(*)(const number_t &,const number_t &)> function_map = {
    {'*', mul},
    {'/', div},
    {'+', add},
    {'-', sub}
};

void process_stack(stack<pair<number_t, char> > &operations,
                   number_t current_number,
                   char operation) {
    while (!operations.empty()) {
        const char op_in_stack = operations.top().second;
        if (priority_map[operation] > priority_map[op_in_stack]) {
            break;
        }
        const number_t num_in_stack = operations.top().first;
        operations.pop();
        current_number = function_map[op_in_stack](num_in_stack, current_number);
    }
    operations.push({current_number, operation});
}

signed main() {
    int c;
    number_t current_number = 0;
    stack<pair<number_t, char> > operations;
    while ((c = getchar()) && c != EOF && c != '\n') {
        if (isdigit(c)) {
            current_number *= 10;
            current_number += c - '0';
        } else {
            map<char, priority_t>::iterator it = priority_map.find(c);
            if (it == priority_map.end()) {
                continue;
            }
            process_stack(operations, current_number, c);
            current_number = 0;
        }
    }
    process_stack(operations, current_number, 0);
    current_number = operations.top().first;
    cout << current_number << endl;
    return 0;
}

»
6 лет назад, # |
Rev. 17   Проголосовать: нравится 0 Проголосовать: не нравится

The following is yet another stack-based possible solution for computing the value of the arithmetic expression. It is assumed that expression has no syntax error, i.e. the stack should contain after parsing the expression an odd number of items whose types alternate consecutively between operand (non-negative integer) and operator ( '*', '+', '-' or '/' ), and the top item of the stack should be an operand.

#include <bits/stdc++.h>

using namespace std;

struct expression_t: stack< int >
{
    expression_t()
    {
        string s; getline( cin, s ); int n = s.size();

        const auto get_next_token = [ s, n ] ( int &i )
        {
            while( i < n and isspace( s[ i ] ) )
                i++;

            return i < n;
        };

        for( int i = 0, op; get_next_token( i ); push( op ) )
            if ( isdigit( op = s[ i++ ] ) )
                for( op -= '0'; i < n and isdigit( s[ i ] ); op *= 10, op += s[ i++ ] - '0' );
    }

    int value()
    {
        int op2 = top(); pop();

        if ( empty() )
            return op2;

        int op1, operation = top(); pop();

        switch( operation )
        {
        case '*': case '/':
            op1 = top(), pop();

            if ( operation == '*' )
                op1 *= op2;
            else
                op1 /= op2;

            break;

        default:
            op1 = value();

            if ( operation == '+' )
                op1 += op2;
            else
                op1 -= op2;
        }

        push( op1 ); return value();
    }
};

int main()
{
    expression_t expression; cout << expression.value();
}