中缀表达式转后缀表达式-C语言，Java
使用堆栈进行表达式的堆栈将中缀（Infix）表达式转换成后缀（postfix）表达式
例 （1）8+4-6*2用后缀表达式表示为：8 4 + 6 2 * -
（2）2*(3+5)+7/1-4用后缀表达式表示为：2 3 5 + * 7 1 / + 4 -
C语言：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_INIT_SIZE 100 // 存储空间初始化分配量
#define STACKINCREMENT 10 // 存储空间分配增量
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int Status;
typedef char SElemType;
typedef struct{
SElemType * base; // 在栈构造之前和销毁之后，base 的值为 NULL
SElemType * top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}SqStack;
static char input[] = "2*(3+5)+7/1-4"; // 静态的中缀表达式
static char output[100]; // 静态的后缀表达式
static int outputlength = 0; // 静态的后缀表达式字符串长度
void gotOper(SqStack &S, char opThis, int prec1); // 声明函数
void gotParen(SqStack &S);
Status InitStack(SqStack &S, int max)
{
// 构造一个空栈
S.base = (SElemType *)malloc(max*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); // 存储分配失败
S.top = S.base;
S.stacksize = max;
return OK;
}
Status GetTop(SqStack S, SElemType &e)
{
// 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK ，否则返回 ERROR
if(S.top == S.base)
return ERROR;
e = *(S.top-1);
return OK;
}
Status Push(SqStack &S, SElemType e)
{
// 插入元素 e 为新的栈顶元素
if(S.top - S.base >= S.stacksize){ // 栈满了，追加存储空间
S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
// 若栈不空，则删除 S 的栈顶元素， 用 e 返回其值，并返回 OK ，否则返回 ERROE
if(S.top == S.base)
return ERROR;
e = *(--S.top);
return OK;
}
Status IsEmpty(SqStack S)
{
// 若栈为空返回 OK， 否则返回 ERROR
if(S.top == S.base)
return OK;
return ERROR;
}
int main()
{
SqStack stack;
InitStack(stack, strlen(input)); // 初始化栈
for(int i = 0;i < strlen(input);i++){ // 得到后缀表达式
char ch = input[i];
switch(ch){
case '+':
case '-':
gotOper(stack, ch, 1);
break;
case '*':
case '/':
gotOper(stack, ch, 2);
break;
case '(':
Push(stack, ch);
break;
case ')':
gotParen(stack);
break;
default: // 遇到数字添加在 output 后面即可
output[outputlength++] = ch;
break;
}
}
while(!IsEmpty(stack)){ // 把栈中最后的运算符添加在 output 后面
char popchar;
Pop(stack, popchar);
output[outputlength++] = popchar;
}
printf("Infix is : %s
", input);
printf("Postfix is : ");
for(int i = 0;i < outputlength;i++)
printf("%c ", output[i]);
return 0;
}
void gotParen(SqStack &S) // 处理回圆括号
{
while(!IsEmpty(S)){
char opTop;
Pop(S, opTop);
if(opTop == '(') // 如果遇到 ( 括号就结束了
break;
else{ // 否则把运算符添加到 output 后面
output[outputlength++] = opTop;
}
}
}
void gotOper(SqStack &S, char opThis, int prec1) // 处理运算符
{
while(!IsEmpty(S)){ // 判断栈是否为空，不为空进行操作
char opTop;
Pop(S, opTop);
if(opTop == '('){ // 如果栈顶是 ( 不做操作 因为括号优先
Push(S, opTop);
break;
}else{
int prec2;
if(opTop == '-' || opTop == '+') // 判断栈顶是 +- 还是 */
prec2 = 1;
else
prec2 = 2;
// 如果栈顶是 +- ，当前字符是 */ ，+- 栈顶优先级低，继续保留在栈里面
if(prec2 < prec1) {
Push(S, opTop);
break;
//否则，栈顶与当前字符一样，或者栈顶是 */ ，当前字符是 +- ，栈顶优先级高，添加在 output 后面
} else {
output[outputlength++] = opTop;
}
}
}
Push(S, opThis); //将当前字符放在栈中
}
/* Code Running Results
input: 2*(3+5)+7/1-4
output: 2 3 5 + * 7 1 / + 4 -
*/
C语言栈使用的链表形式，而接下来Java语中的栈使用数组形式。
Java：
public class InfixExpressionToPostfixExpression {
private Stack theStack;
private String input;
private String output = "";
//构造函数，创建 Stack 类
public InfixExpressionToPostfixExpression(String in){
input = in;
int stackSize = in.length();
theStack = new Stack(stackSize);
}
//主函数
public static void main(String[] args) {
String input = "2*(3+5*2)+7/1-4";
String output;
InfixExpressionToPostfixExpression theTran = new InfixExpressionToPostfixExpression(input);
output = theTran.doTrans();
System.out.println("Infix is " + input);
System.out.println("Postfix is " + output);
}
//得到后缀表达式
public String doTrans() {
for(int i = 0;i < input.length();i++) {
char ch = input.charAt(i);
switch(ch) {
case '+':
case '-':
gotOper(ch, 1);
break;
case '*':
case '/':
gotOper(ch, 2);
break;
case '(':
theStack.push(ch);
break;
case ')':
gotParen();
break;
//遇到数字添加在 output 后面即可
default:
output = output + " " + ch;
break;
}
}
//把栈中最后的运算符添加在 output 后面
while( !theStack.isEmpty() )
output = output + " " + theStack.pop();
return output;
}
//处理运算符
public void gotOper(char opThis, int prec1) {
//判断栈是否为空，不为空进行操作
while( !theStack.isEmpty() ) {
char opTop = theStack.pop();
//如果栈顶是 ( 不做操作 因为括号优先
if(opTop == '(') {
theStack.push(opTop);
break;
} else {
int prec2;
//判断栈顶是 +- 还是 */
if(opTop == '-' || opTop == '+')
prec2 = 1;
else
prec2 = 2;
//如果栈顶是 +- ，当前字符是 */ ，+- 栈顶优先级低，继续保留在栈里面
if(prec2 < prec1) {
theStack.push(opTop);
break;
//否则，栈顶与当前字符一样，或者栈顶是 */ ，当前字符是 +- ，栈顶优先级高，添加在 output 后面
} else
output = output + " " + opTop;
}
}
//将当前字符放在栈中
theStack.push(opThis);
}
//处理回圆括号
public void gotParen() {
while( !theStack.isEmpty() ) {
char opTop = theStack.pop();
//如果遇到 ( 括号就结束了
if( opTop == '(')
break;
//否则把运算符添加到 output 后面
else
output = output + " " + opTop;
}
}
}
//栈类, 用来保存运算符和圆括号
class Stack {
private int maxSize;
private char [] stackArray;
private int top;
//初始化栈的构造函数，此时栈为空
public Stack(int max) {
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
//入栈
public void push(char j) {
stackArray[++top] = j;
}
//出栈并返回出栈
public char pop() {
return stackArray[top--];
}
//返回栈顶元素
public char peek() {
return stackArray[top];
}
//判断栈是否为空
public boolean isEmpty() {
return (top == -1);
}
}
/* Code Running Results
Infix is 2*(3+5*2)+7/1-4
Postfix is 2 3 5 2 * + * 7 1 / + 4 -
*/