alex/likemath.ru
1
0
Fork 0
mirror of https://github.com/AlekseyLobanov/AlekseyLobanov.github.io.git synced 2026-01-11 20:52:01 +03:00
Code Issues Projects Releases Wiki Activity
Files
master
likemath.ru/posts/eshchio-odno-vychislenie-vyrazhenii/index.html
Aleksey Lobanov d2d31dfeff New version
2020-11-04 00:23:14 +03:00

75 lines
8.8 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!DOCTYPE html><!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]--><!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]--><!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]--><!--[if gt IE 8]><!--><html class=no-js> <!--<![endif]--> <head><meta charset=utf-8><meta http-equiv=X-UA-Compatible content="IE=edge,chrome=1"><title>Ещё одно вычисление выражений</title><meta name=description content><meta name=viewport content="width=device-width"><link rel=stylesheet href=../../theme/css/normalize.css><link href="https://fonts.googleapis.com/css?family=Forum|Oswald|PT+Sans|Philosopher|Ubuntu+Mono" rel=stylesheet><link rel=stylesheet href=../../theme/css/font-awesome.min.css><link rel=stylesheet href=../../theme/css/main.css><link rel=stylesheet href=../../theme/css/blog.css><link rel=stylesheet href=../../theme/css/github.css><link href=https://likemath.ru/feeds/all.atom.xml type=application/atom+xml rel=alternate title="Блог 529 Atom Feed"><link href=https://likemath.ru/feeds/all.rss.xml type=application/rss+xml rel=alternate title="Блог 529 RSS Feed"><script src=../../theme/js/vendor/modernizr-2.6.2.min.js></script></head> <body> <!--[if lt IE 7]>
<p class="chromeframe">You are using an <strong>outdated</strong> browser. Please <a href="http://browsehappy.com/">upgrade your browser</a> or <a href="http://www.google.com/chromeframe/?redirect=true">activate Google Chrome Frame</a> to improve your experience.</p>
<![endif]--> <div id=wrapper> <header id=sidebar class=side-shadow> <hgroup id=site-header> <a id=site-title href=../..><h2><i class=icon-pencil></i> Блог 529</h2></a> <p id=site-desc> Project Euler и остальное </p> </hgroup> <nav> <ul id=nav-links> <li><a href=../../ >Главная</a></li> <li><a href=../../pages/projects.html>Мои проекты</a></li> <li><a href=../../pages/about.html>Об авторе</a></li> <li><a href=../../feeds/feed.atom.xml>Atom feed</a></li> </ul> </nav> <footer id=site-info> <p> Powered by Pelican. </p> </footer></header> <div id=post-container> <ol id=post-list> <li> <article class=post-entry> <header class=entry-header> <time class=post-time datetime=2015-07-03T17:40:00+03:00 pubdate> Пт 03 июля 2015 </time> <a href=../../posts/eshchio-odno-vychislenie-vyrazhenii/ rel=bookmark><h1>Ещё одно вычисление&nbsp;выражений</h1></a> </header> <section class=post-content> <p>Задачка кажется не очень сложной, даже, если не знать как её делать (я не знал). Целью является быстрое вычисление чего-то типа <code>4 * ( 5 + 7 ^ 4)</code>. Для это я парсил исходную строку в список токенов, а затем непосредственно вычислял, что&nbsp;получится.</p> <p>Я решил, что проще всего будет реализовать (а мне потом и понять) алгоритм, когда после каждого действия будет выполняться некий &#8220;хороший&#8221; инвариант. Первое что приходит в голову &#8212; это то, что истинность выражение после выполнения операции не меняется (<span class=caps>TITO</span> соблюдается). То есть выражение <code>3 + 5</code> можно заменить на <code>8</code> или хотя бы на <code>4 * 2</code>.</p> <p>Непосредственно сама обработка является несколькими проходами, так что в каждом проходе мы избавляемся от операций одного приоритета. <code>4 + 5 * 3</code> заменяется на <code>4 + 15, 7 - 5 * 2^3</code> заменяется на <code>7 - 5*8</code>. Таким образом, каждый цикл тривиален, и легко задавать приоритеты&nbsp;операций.</p> <p>Если использовать один список как контейнер для токенов и при работе изменять непосредственно его, сохраняя указанные инварианты, то сложность получается <span class=math>\(O\left( N \right)\)</span>, где <span class=math>\(N\)</span> &#8212; число&nbsp;токенов.</p> <p>Времени на непосредственно кодирование ушло часа три-четыре, но в это время не входит продумывание мелких&nbsp;деталей.</p> <p>Всё написано на C++11. Исходники лежат на <a href=https://github.com/AlekseyLobanov/ExprEvaler>GitHub</a> и <a href=https://bitbucket.org/Begemot23/exprevaler>BitBucket</a>.</p> <script type=text/javascript>if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
var align = "center",
indent = "0em",
linebreak = "false";
if (false) {
align = (screen.width < 768) ? "left" : align;
indent = (screen.width < 768) ? "0em" : indent;
linebreak = (screen.width < 768) ? 'true' : linebreak;
}
var mathjaxscript = document.createElement('script');
mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
mathjaxscript.type = 'text/javascript';
mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=TeX-AMS-MML_HTMLorMML';
var configscript = document.createElement('script');
configscript.type = 'text/x-mathjax-config';
configscript[(window.opera ? "innerHTML" : "text")] =
"MathJax.Hub.Config({" +
" config: ['MMLorHTML.js']," +
" TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'none' } }," +
" jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
" extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
" displayAlign: '"+ align +"'," +
" displayIndent: '"+ indent +"'," +
" showMathMenu: true," +
" messageStyle: 'normal'," +
" tex2jax: { " +
" inlineMath: [ ['\\\\(','\\\\)'] ], " +
" displayMath: [ ['$$','$$'] ]," +
" processEscapes: true," +
" preview: 'TeX'," +
" }, " +
" 'HTML-CSS': { " +
" availableFonts: ['STIX', 'TeX']," +
" preferredFont: 'STIX'," +
" styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
" linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
" }, " +
"}); " +
"if ('default' !== 'default') {" +
"MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"}";
(document.body || document.getElementsByTagName('head')[0]).appendChild(configscript);
(document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script> </section> <hr> <aside class=post-meta> <p>Категория: <a href=../../category/proekty.html>Проекты</a></p> <p>Теги: <a href=../../tag/proekt.html>проект</a>, </p> </aside> <hr> </article> </li> </ol> </div> </div> <script type=text/javascript>
var _paq = _paq || [];
_paq.push(['trackPageView']);
_paq.push(['enableLinkTracking']);
(function() {
var u="https://piwik.likemath.ru/";
_paq.push(['setTrackerUrl', u+'piwik.php']);
_paq.push(['setSiteId', '1']);
var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0];
g.type='text/javascript'; g.async=true; g.defer=true; g.src=u+'piwik.js'; s.parentNode.insertBefore(g,s);
})();
</script> <script src=../../theme/js/main.js></script> </body> </html>
Reference in New Issue View Git Blame Copy Permalink