postfixcal.htm
来自「“常见程式演算”主要收集一些常见的程式练习题目」· HTM 代码 · 共 219 行
HTM
219 行
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>后序式的运算</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 后序式的运算</a></h1>
说明
将 <a class="wikilink" href="InFixPostfix.htm">中序式转换为后序式</a>
的好处是，不用处理运算子先后顺序问题，只要依序由运算式由前往后读取即可。
<h2> 解法</h2>
运算时由后序式的前方开始读取，遇到运算元先存入堆叠，如果遇到运算子，则由堆叠中取出两个运算元进行对应的运算，然后将结果存回堆叠，如果运算式读取完
毕，那么堆叠顶的值就是答案了，例如我们计算12+34+*这个运算式（也就是(1+2)*(3+4)）：
<table border="1" width="50%">
<tbody>
<tr>
<td align="left" valign="top"><small>读取 </small></td>
<td align="left" valign="top"><small>堆叠 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>1 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>2 </small></td>
<td align="left" valign="top"><small>1 2 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>+ </small></td>
<td align="left" valign="top"><small>3 // 1+2 后存回 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>3 </small></td>
<td align="left" valign="top"><small>3 3 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>4 </small></td>
<td align="left" valign="top"><small>3 3 4 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>+ </small></td>
<td align="left" valign="top"><small>3 7 // 3+4 后存回 </small></td>
</tr>
<tr>
<td align="left" valign="top"><small>* </small></td>
<td align="left" valign="top"><small>21 // 3 * 7 后存回</small></td>
</tr>
</tbody>
</table>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>void evalPf(char*); <br>double cal(double, char, double); <br><br>int main(void) { <br> char input[80]; <br><br> printf("输入后序式："); <br> scanf("%s", input); <br> evalPf(input); <br><br> return; <br>} <br><br>void evalPf(char* postfix) { <br> double stack[80] = {0.0}; <br> char temp[2]; <br> char token; <br> int top = 0, i = 0; <br><br> temp[1] = '\0'; <br><br> while(1) { <br> token = postfix[i]; <br> switch(token) { <br> case '\0': <br> printf("ans = %f\n", stack[top]); <br> return; <br> case '+': case '-': case '*': case '/': <br> stack[top-1] = <br> cal(stack[top-1], token, stack[top]); <br> top--; <br> break; <br> default: <br> if(top < sizeof(stack) / sizeof(float)) { <br> temp[0] = postfix[i]; <br> top++; <br> stack[top] = atof(temp); <br> } <br> break; <br> } <br> i++; <br> } <br>} <br><br>double cal(double p1, char op, double p2) { <br> switch(op) { <br> case '+': <br> return p1 + p2; <br> case '-': <br> return p1 - p2; <br> case '*': <br> return p1 * p2; <br> case '/': <br> return p1 / p2; <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class InFix {<br> private static int priority(char op) { <br> switch(op) { <br> case '+': case '-': <br> return 1; <br> case '*': case '/': <br> return 2;<br> default: <br> return 0;<br> } <br> }<br> <br> public static char[] toPosfix(char[] infix) {<br> char[] stack = new char[infix.length]; <br> char[] postfix = new char[infix.length];<br> char op; <br><br> StringBuffer buffer = new StringBuffer();<br><br> int top = 0;<br> for(int i = 0; i < infix.length; i++) { <br> op = infix[i]; <br> switch(op) { <br> // 运算子堆叠 <br> case '(': <br> if(top < stack.length) { <br> top++; <br> stack[top] = op; <br> } <br> break; <br> case '+': case '-': case '*': case '/': <br> while(priority(stack[top]) >= <br> priority(op)) { <br> buffer.append(stack[top]);<br> top--; <br> } <br> // 存入堆叠 <br> if(top < stack.length) { <br> top++; <br> stack[top] = op; <br> } <br> break; <br> // 遇 ) 输出至 ( <br> case ')': <br> while(stack[top] != '(') { <br> buffer.append(stack[top]);<br> top--; <br> } <br> top--; // 不输出( <br> break; <br> // 运算元直接输出 <br> default: <br> buffer.append(op);<br> break; <br> } <br> } <br> <br> while(top > 0) { <br> buffer.append(stack[top]);<br> top--; <br> }<br> <br> return buffer.toString().toCharArray();<br> }<br><br> private static double cal(double p1, char op, double p2) { <br> switch(op) { <br> case '+': <br> return p1 + p2; <br> case '-': <br> return p1 - p2; <br> case '*': <br> return p1 * p2; <br> case '/': <br> return p1 / p2; <br> }<br> return 0.0;<br> }<br> <br> public static double eval(char[] postfix) {<br> double[] stack = new double[postfix.length]; <br> char token; <br> int top = 0; <br><br> for(int i = 0; i < postfix.length; i++) { <br> token = postfix[i]; <br> switch(token) { <br> case '+': case '-': case '*': case '/': <br> stack[top-1] = <br> cal(stack[top-1], token, stack[top]); <br> top--; <br> break; <br> default: <br> if(top < stack.length) { <br> char temp = postfix[i]; <br> top++; <br> stack[top] = <br> Double.parseDouble(<br> String.valueOf(temp)); <br> } <br> break; <br> } <br> } <br><br> return stack[top];<br> }<br> <br> public static void main(String[] args) {<br> String infix = "(1+2)*(3+4)";<br> <br> System.out.println(InFix.eval(<br> InFix.toPosfix(infix.toCharArray())));<br> }<br>}</pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?