中缀表达式转后缀表达式然后计算结果（由王道考研b站视频中数据结构P28 3.3.2栈应用）

<p>//注意该文件为.cc文件，c和c++杂交的，但是比较好理解，可以才 .cc文件中运行</p><p>#define _CRT_SECURE_NO_WARNINGS 1</p><p>#include &lt;stdio.h&gt;</p><p>#include &lt;stdlib.h&gt;</p><p>#include &lt;string.h&gt;</p><p>#define ElemTypeD int</p><p>#define ElemTypeC char</p><p>struct NodeD</p><p>{</p><p> ElemTypeD data;</p><p> struct NodeD* next;</p><p>};</p><p>typedef struct NodeD NodeD;</p><p>typedef struct NodeD* StackD;</p><p>struct NodeC</p><p>{</p><p> ElemTypeC data;</p><p> struct NodeC* next;</p><p>};</p><p>typedef struct NodeC NodeC;</p><p>typedef struct NodeC* StackC;</p><p>bool InitStackD(StackD&amp; SD)</p><p>{</p><p> SD = (NodeD*)malloc(sizeof(NodeD));</p><p> if (SD == NULL)</p><p> {</p><p> return false;</p><p> }</p><p> SD-&gt;next = NULL;</p><p> return true;</p><p>}</p><p>bool InitStackC(StackC&amp; SC)</p><p>{</p><p> SC = (NodeC*)malloc(sizeof(NodeC));</p><p> if (SC == NULL)</p><p> {</p><p> return false;</p><p> }</p><p> SC-&gt;next = NULL;</p><p> return true;</p><p>}</p><p>bool IsEmptyD(StackD SD)</p><p>{</p><p> return (SD-&gt;next == NULL);</p><p>}</p><p>bool IsEmptyC(StackC SC)</p><p>{</p><p> return (SC-&gt;next == NULL);</p><p>}</p><p>bool PushD(StackD&amp; SD, ElemTypeD e)</p><p>{</p><p> NodeD* s = (NodeD*)malloc(sizeof(NodeD));</p><p> if (s == NULL)</p><p> {</p><p> return false;</p><p> }</p><p> s-&gt;data = e;</p><p> s-&gt;next = SD-&gt;next;</p><p> SD-&gt;next = s;</p><p> return true;</p><p>}</p><p>bool PushC(StackC&amp; SC, ElemTypeC e)</p><p>{</p><p> NodeC* s = (NodeC*)malloc(sizeof(NodeC));</p><p> if (s == NULL)</p><p> {</p><p> return false;</p><p> }</p><p> s-&gt;data = e;</p><p> s-&gt;next = SC-&gt;next;</p><p> SC-&gt;next = s;</p><p> return true;</p><p>}</p><p>bool PopD(StackD&amp; SD, ElemTypeD&amp; e)</p><p>{</p><p> if (IsEmptyD(SD))</p><p> {</p><p> return false;</p><p> }</p><p> NodeD* p = SD-&gt;next;</p><p> e = p-&gt;data;</p><p> SD-&gt;next = p-&gt;next;</p><p> free(p);</p><p> return true;</p><p>}</p><p>bool PopC(StackC&amp; SC, ElemTypeC&amp; e)</p><p>{</p><p> if (IsEmptyC(SC))</p><p> {</p><p> return false;</p><p> }</p><p> NodeC* p = SC-&gt;next;</p><p> e = p-&gt;data;</p><p> SC-&gt;next = p-&gt;next;</p><p> free(p);</p><p> return true;</p><p>}</p><p>bool GetElemC(StackC SC, ElemTypeC&amp; e)</p><p>{</p><p> if (IsEmptyC(SC))</p><p> {</p><p> return false;</p><p> }</p><p> e = SC-&gt;next-&gt;data;</p><p> return true;</p><p>}</p><p>bool IsStop(StackC SC)</p><p>{</p><p> ElemTypeC e;</p><p> int ret = GetElemC(SC, e);</p><p> if (ret == 0 || e == '(')</p><p> {</p><p> return true;</p><p> }</p><p> else</p><p> {</p><p> return false;</p><p> }</p><p>}</p><p>bool IsStopPlus(StackC SC)</p><p>{</p><p> ElemTypeC e;</p><p> int ret = GetElemC(SC, e);</p><p> if (ret == 0 || e == '(' || e == '+' || e == '-')</p><p> {</p><p> return true;</p><p> }</p><p> else</p><p> {</p><p> return false;</p><p> }</p><p>}</p><p>bool Operation(StackD&amp; SD, ElemTypeC now)</p><p>{</p><p> ElemTypeD b;</p><p> ElemTypeD a;</p><p> int ret1 = PopD(SD, b);</p><p> int ret2 = PopD(SD, a);</p><p> if (ret1 == 0 || ret2 == 0)</p><p> {</p><p> return false;</p><p> }</p><p> ElemTypeD sum = 0;</p><p> if (now == '+')</p><p> {</p><p> sum = a + b;</p><p> }</p><p> if (now == '-')</p><p> {</p><p> sum = a - b;</p><p> }</p><p> if (now == '*')</p><p> {</p><p> sum = a * b;</p><p> }</p><p> if (now == '/')</p><p> {</p><p> sum = a / b;</p><p> }</p><p> PushD(SD, sum);</p><p> return true;</p><p>}</p><p>void JudgeChar(StackD&amp; SD, StackC&amp; SC, char e)</p><p>{</p><p> if (e == '(')</p><p> {</p><p> return;</p><p> }</p><p> if (e == ')' || e == '+' || e == '-')</p><p> {</p><p> while (!IsStop(SC))</p><p> {</p><p> ElemTypeC now;</p><p> PopC(SC, now);</p><p> Operation(SD, now);</p><p> }</p><p> if (e == ')')</p><p> {</p><p> ElemTypeC need;</p><p> PopC(SC, need);</p><p> }</p><p> return;</p><p> }</p><p> if (e == '*' || e == '/')</p><p> {</p><p> while (!IsStopPlus(SC))</p><p> {</p><p> ElemTypeC now;</p><p> PopC(SC, now);</p><p> Operation(SD, now);</p><p> }</p><p> return;</p><p> }</p><p>}</p><p>bool func(char* str, int len)</p><p>{</p><p> StackD SD;</p><p> StackD temp;</p><p> StackC SC;</p><p> InitStackD(SD);</p><p> InitStackD(temp);</p><p> InitStackC(SC);</p><p> for (int i = 0; i &lt; len; i++)</p><p> {</p><p> if (str[i] &gt;= 48 &amp;&amp; str[i] &lt;= 57)</p><p> {</p><p> PushD(temp, str[i] - '0');</p><p> }</p><p> else if (str[i] == '#')</p><p> {</p><p> ElemTypeD took = 0;</p><p> ElemTypeD sum = 0;</p><p> ElemTypeD i = 1;</p><p> while (!IsEmptyD(temp))</p><p> {</p><p> PopD(temp, took);</p><p> sum += took * i;</p><p> i *= 10;</p><p> }</p><p> PushD(SD, sum);</p><p> }</p><p> else</p><p> {</p><p> JudgeChar(SD, SC, str[i]);</p><p> if (str[i] != ')')</p><p> {</p><p> PushC(SC, str[i]);</p><p> }</p><p> }</p><p> }</p><p> while (!IsEmptyC(SC))</p><p> {</p><p> ElemTypeC fu = '+';</p><p> JudgeChar(SD, SC, fu);</p><p> }</p><p> ElemTypeD ans;</p><p> PopD(SD, ans);</p><p> printf("计算结果为%d\n", ans);</p><p> return (IsEmptyD(SD) &amp;&amp; IsEmptyC(SC));</p><p>}</p><p>int main</p><p>{</p><p> char str[100];</p><p> scanf("请输入中缀表达式。\n");</p><p> scanf("注意每个数字后面需要加上#\n");</p><p> scanf("如 333#*(4#+9#/3#*8#) \n");</p><p> scanf("但无法输入有小数的式子 如1.23\n");</p><p> scanf("%s", str);</p><p> int len = strlen(str);</p><p> int ret = func(str, len);</p><p> if (!ret)</p><p> {</p><p> printf("输入表达式有问题\n");</p><p> }</p><p> system("pause");</p><p> return 0;</p><p>}</p><h3>
        <p>
                <br />
        </p>
        <p>
                沪学网考研课程全免费，首家、全免费、全网实时更新！
        </p>
<img src="https://www.huxuewang.com/00.png" alt="" />
</h3>
<p>
        <br />
</p>