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

75 lines
8.8 KiB
HTML
Raw Permalink Blame History

<!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