Строковый калькулятор

@Penelent · 14.09.2015, 17:18. **Показов** 4099. **Ответов** 9

Студворк — интернет-сервис помощи студентам

где то очень давно видел алгоритм строкового калькулятора на двух стеках (в одном числа, в другом операции), помогите пожалуйста найти, весь яндекс перерыл... везде только обратная польская запись, а она на одном строковом стеке

@gazlan · 14.09.2015, 19:01

Evaluating infix arithmetic expressions with two stacks C++ implementation
Executing infix arithmetic expressions.cpp

I made the simplifying assumption that tokens in the input expression are separated by spaces in order to simplify tokenization. The evaluation of expressions is done with two stacks, one for operands and the other for operators. The program combines the algorithms for infix-to-postfix conversion and postfix evaluation, eliminates the production of intermediate postfix expression and requires just one scan of the input infix expression.

@srdi · 14.09.2015, 19:47

Может с помощу польской нотации?

@Penelent · 14.09.2015, 20:44 **[ТС]**

gazlan, не работает же

srdi, прямая? тоже врятли, там кажется тоже один стек

Добавлено через 5 минут
у меня имеется два стека с операциями и числами, все записано по порядку как было в строке, например "1 + 2 * 3" в стеках: операции { '+', '*' } числа { 1, 2, 3 }, забыл самое главное в строке нет скобок, вот что мне дальше делать? как посчитать исходя из этих стеков? просто у меня уже так запрограммировано, куча кода за этим стоит, я не хочу переписывать все под обратную польскую запись или еще что то

Добавлено через 37 минут
ладно пофиг кажется сам придумал

@Shamil1 · 14.09.2015, 21:17

Эх, хотел написать калькулятор "за 5 минут", но за 5 минут не вышло.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
static readonly Dictionary<string,int> priorities = new Dictionary<string,int> 
{
    {"(", 0}, {")", 1}, {"+", 2}, {"-", 2}, {"*", 3}, {"/", 3}, {"^", 4},     
};
IEnumerable<Token> InfixToPostfix(IEnumerable<Token> tokens)
{
    Stack<Token> operators = new Stack<Token>();
    foreach(Token token in tokens)
    {
        if(token.IsNumber)
        {
            yield return token;
            continue;
        }
        int priority = priorities[token.Operator];
        while(priority > 0 && operators.Count > 0 && priority <= priorities[operators.Peek().Operator])
        {
            yield return operators.Pop();
        }
        operators.Push(token);
        if(priorities[operators.Peek().Operator] == 1)
        {
            operators.Pop();
            operators.Pop();
        }
    }
    while(operators.Count > 0)
        yield return operators.Pop();
}
 
double PostfixCalc(IEnumerable<Token> tokens)
{
    Stack<double> numbers = new Stack<double>();
    foreach(Token token in tokens)
    {
        if(token.IsNumber)
        {
            numbers.Push(token.Value);
            continue;
        }
        double operand2 = numbers.Pop();
        double operand1 = numbers.Pop();
        switch(token.Operator)
        {
            case "+":
                numbers.Push(operand1 + operand2);
                break;
            case "-":
                numbers.Push(operand1 - operand2);
                break;
            case "*":
                numbers.Push(operand1 * operand2);
                break;
            case "/":
                numbers.Push(operand1 / operand2);
                break;
            case "^":
                numbers.Push(Math.Pow(operand1, operand2));
                break;
            default:
                throw new InvalidOperationException(string.Format("Unknow operator '{0}'", token.Operator));
        }
    }
    return numbers.Pop();
}
 
IEnumerable<Token> ParseTokens(string input)
{
    for(int i = 0; i < input.Length; i++)
    {
        char c = input[i];
        if(char.IsWhiteSpace(c))
            continue;
        
        if(priorities.ContainsKey(c.ToString()))
        {
            yield return new Token { Operator = c.ToString() }; 
            continue;       
        }
        if(char.IsDigit(c))
        {
            yield return new Token { Value = ReadNumber(input, ref i) };
            i--;
            continue;
        }
        throw new FormatException(string.Format("Unexpected character '{0}' at position {1}.", c, i));  
    }
}
 
static readonly NumberFormatInfo numberFormatInfo = new NumberFormatInfo { NumberDecimalSeparator = "." };
double  ReadNumber(string input, ref int i)
{
    StringBuilder number = new StringBuilder();
    while(i < input.Length && char.IsNumber(input[i])) 
        number.Append(input[i++]);
    if(i < input.Length && input[i] == '.')
    {
        number.Append(input[i++]);
        while(i < input.Length && char.IsNumber(input[i])) 
            number.Append(input[i++]);
    }
    return double.Parse(number.ToString(), numberFormatInfo);   
}
 
struct Token
{
    public string Operator;
    public double Value;
    public bool IsNumber { get { return Operator == null; } }
}

Ссылку в сообщении#2 не открывал, но, судя по названию, у меня примерно то же, что и там.

Добавлено через 4 минуты

Сообщение от Penelent

у меня имеется два стека с операциями и числами, все записано по порядку как было в строке, например "1 + 2 * 3" в стеках: операции { '+', '*' } числа { 1, 2, 3 }, забыл самое главное в строке нет скобок, вот что мне дальше делать? как посчитать исходя из этих стеков?

Упростить задачу, сведя её к предыдущей (собрать два стека в один поток токенов)

@gazlan · 14.09.2015, 21:40

Сообщение от Penelent

не работает

Работает (с целыми числами).

А так, всем советую EVAL.C - A simple mathematical expression evaluator in C

Не по теме:

Доработанный код использовал здесь (и еще много где).

@Penelent · 15.09.2015, 08:44 **[ТС]**

Shamil1, пока не разбирался, а куда пихать собственно входную строку?

короче вот, шокирует своей говнокодностью, слабонервным лучше не смотреть

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
public static class Expression
{
    private struct MathFunction
    {
        public string Name;
        public Func<double, double> Function;
    }
 
    private static List<MathFunction> Functions = new List<MathFunction>()
    {
        new MathFunction() { Name = "sin", Function = a => Math.Sin(a) },
        new MathFunction() { Name = "cos", Function = a => Math.Cos(a) },
        new MathFunction() { Name = "tg", Function = a => Math.Tan(a) },
        new MathFunction() { Name = "ctg", Function = a => Math.Cos(a) / Math.Sin(a) },
        new MathFunction() { Name = "ln", Function = a => Math.Log10(a) },
        new MathFunction() { Name = "exp", Function = a => Math.Exp(a) }
    };
 
    public static double Solve(string expr)
    {
        if (string.IsNullOrWhiteSpace(expr))
            throw new ArgumentException();
        expr = expr.Replace(" ", string.Empty);
        expr = expr.Replace("\t", string.Empty);
        expr = expr.ToLower();
        return SolveExpr(expr);
    }
 
    private static int NumberParse(string s)
    {
        for (int i = 0; i < s.Length; i++)
            if (!(char.IsDigit(s, i) || s[i] == '.'))
                return i;
        return s.Length;
    }
 
    private static int ParenthesesParse(string s)
    {
        var open = new List<int>();
        var close = new List<int>();
 
        open.Add(0);
 
        for (int i = 1; i < s.Length && open.Count != close.Count; i++)
        {
            if (s[i] == '(')
                open.Add(i);
            if (s[i] == ')')
                close.Add(i);
        }
 
        if (open.Count != close.Count)
            throw new ArgumentException();
 
        return close[close.Count - 1] + 1;
    }
 
    private static int FuncParse(string s)
    {
        for (int i = 0; i < s.Length; i++)
        {
            if (!char.IsLetter(s, i))
            {
                var name = s.Substring(0, i);
                var r = from f in Functions
                        where f.Name.Equals(name)
                        select f;
                if (r.Count() != 0)
                    return name.Length;
            }
        }
        throw new ArgumentException();
    }
 
    private static string FindExpr2(string e, out int l)
    {
        if (char.IsDigit(e, 0))
        {
            l = NumberParse(e);
            return e.Substring(0, l);
        }
 
        if (e[0] == '(')
        {
            l = ParenthesesParse(e);
            return e.Substring(0, l);
        }
 
        if (char.IsLetter(e, 0))
        {
            l = FuncParse(e);
            var tmp = e.Substring(l);
            l += ParenthesesParse(tmp);
            return e.Substring(0, l);
        }
 
        throw new ArgumentException();
    }
 
    private static void FindExpressions(string expr, List<string> expressions, List<char> operations)
    {
        for (int i = 0; i < expr.Length; i++)
        {
            int l = 0;
 
            if (i == 0 && expr[0] == '-')
            {
                var s0 = expr.Substring(1, expr.Length - 1);
                s0 = FindExpr2(s0, out l);
                expressions.Add('-' + s0);
                i += l;
                continue;
            }
 
            if ("+-*/^".Contains(expr[i]))
            {
                operations.Add(expr[i]);
                continue;
            }
 
            var s = expr.Substring(i, expr.Length - i);
            s = FindExpr2(s, out l);
            expressions.Add(s);
            i += l - 1;
        }
    }
 
    private static double SolveExpr(string expr)
    {
        var expressions = new List<string>();
        var operations = new List<char>();
        FindExpressions(expr, expressions, operations);
 
        if (expressions.Count > 1 && operations.Count > 0)
        {
            var results = new List<double>();
 
            foreach (var e in expressions)
                results.Add(SolveExpr(e));
 
            return Simple(results, operations);
        }
        else
        {
            if (expressions.Count == 1 && operations.Count == 0)
            {
                if (char.IsNumber(expressions[0], 0))
                    return double.Parse(expressions[0]);
 
                if (expressions[0][0] == '-')
                {
                    var s = expressions[0].Substring(1);
                    var l = 0;
                    s = FindExpr2(s, out l);
                    if (char.IsDigit(s, 0))
                        return double.Parse('-' + s);
                    else
                        return - SolveExpr(s);
                }
 
                if (expressions[0][0] == '(')
                {
                    expr = expressions[0].Remove(0, 1);
                    expr = expr.Remove(expr.Length - 1, 1);
                    return SolveExpr(expr);
                }
 
                if (char.IsLetter(expressions[0], 0))
                {
                    var i = expressions[0].IndexOf('(');
                    expr = expressions[0].Substring(i + 1, expressions[0].Length - i - 2);
                    var r = SolveExpr(expr);
                    var n = expressions[0].Substring(0, i);
                    var find = from f in Functions
                               where f.Name == n
                               select f;
                    if (find.Count() == 0)
                        throw new ArgumentException();
                    else
                        return find.ElementAt(0).Function(r);
                }
 
                throw new ArgumentException();
            }
            else
                throw new ArgumentException();
        }
    }
 
    private static double Simple(List<double> numbers, List<char> operations)
    {
        for (int i = 0; i < numbers.Count - 1; i++)
        {
            var a = numbers[i];
            var b = numbers[i + 1];
            var c = operations[i];
            
            if (c == '^')
            {
                if (a < 0 && (Math.Floor(b) - b) != 0.0)
                    throw new ArgumentException();
                var num = Math.Pow(a, b);
                numbers.RemoveAt(i);
                numbers.RemoveAt(i);
                operations.RemoveAt(i);
                numbers.Insert(i, num);
            }
        }
 
        for (int i = 0; i < numbers.Count - 1; i++)
        {
            var a = numbers[i];
            var b = numbers[i + 1];
            var c = operations[i];
 
            if (c == '*')
            {
                var num = a * b;
                numbers.RemoveRange(i, 2);
                operations.RemoveAt(i);
                numbers.Insert(i--, num);
            }
 
            if (c == '/')
            {
                if (b == 0.0)
                    throw new ArgumentException();
                var num = a / b;
                numbers.RemoveRange(i, 2);
                operations.RemoveAt(i);
                numbers.Insert(i--, num);
            }
        }
 
        for (int i = 0; i < numbers.Count - 1; i++)
        {
            var a = numbers[i];
            var b = numbers[i + 1];
            var c = operations[i];
 
            if (c == '+')
            {
                var num = a + b;
                numbers.RemoveRange(i, 2);
                operations.RemoveAt(i);
                numbers.Insert(i--, num);
            }
 
            if (c == '-')
            {
                var num = a - b;
                numbers.RemoveRange(i, 2);
                operations.RemoveAt(i);
                numbers.Insert(i--, num);
            }
        }
 
        return numbers[0];
    }
}

@Penelent · 15.09.2015, 12:47 **[ТС]**

+ вариант с интерфейсом

@Penelent · 15.09.2015, 12:54 **[ТС]**

del

@Shamil1 · 15.09.2015, 13:40

Penelent,
У меня там три функции:
ParseTokens - превращает входную строку в поток токенов
PostfixCalc - вычисляет результат для потока токенов в постфиксной записи
InfixToPostfix - переводит поток токенов из инфиксной в постфиксную запись

Поэтому "основную" функцию можно сделать такой:

C#
1
2
3
4
5
6
7
8
9
double Calculate(string input, bool isInfix)
{
    IEnumerable<Token> tokens = ParseTokens(input);
    if(isInfix)
    {
        tokens = InfixToPostfix(tokens);
    }
    return PostfixCalc(tokens);
}

И запускать так:

C#
1
2
3
4
5
void Main()
{
    Calculate(@"3 7.5 * 600 5/+", false).Dump();
    Calculate(@"5*(4+12/3)+3", true).Dump();
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Penelent Заблокирован

	Строковый калькулятор 14.09.2015, 17:18. Показов 4099. Ответов 9 Метки нет (Все метки) где то очень давно видел алгоритм строкового калькулятора на двух стеках (в одном числа, в другом операции), помогите пожалуйста найти, весь яндекс перерыл... везде только обратная польская запись, а она на одном строковом стеке 0

@srdi 0 / 0 / 0 Регистрация: 02.11.2014 Сообщений: 16
	14.09.2015, 19:47
	Может с помощу польской нотации? 0

@Penelent Заблокирован
	14.09.2015, 20:44 [ТС]
	gazlan, не работает же srdi, прямая? тоже врятли, там кажется тоже один стек Добавлено через 5 минут у меня имеется два стека с операциями и числами, все записано по порядку как было в строке, например "1 + 2 * 3" в стеках: операции { '+', '' } числа { 1, 2, 3 }, забыл самое главное в строке нет скобок, вот что мне дальше делать? как посчитать исходя из этих стеков? просто у меня уже так запрограммировано, куча кода за этим стоит, я не хочу переписывать все под обратную польскую запись или еще что то Добавлено через 37 минут* ладно пофиг кажется сам придумал 0

@Penelent Заблокирован
	15.09.2015, 12:54 [ТС]
	del 0