中缀表达式：也就是一般的算术表达式，如"9+(3-1)*3+10/2这样的

后缀表达式：就是将运算符挪到操作数后面，但这样的挪动是有规则的，例如上式转换后缀表达式后是这样的："9 3 1-4*+10 2/+"

中缀转后缀表达式规则：

从左到右遍历中缀表达式中的每一个·数字和符号：

1.如果是操作数就输出，成为后缀表达式的一部分

2.如果是运算符，先判定它与栈顶元素的优先级，如果栈顶元素优先级低比它低或相等，则入栈；

  如果优先级高于它，则出栈当前栈顶元素到后缀表达式中，直到栈顶元素优先级比它高(即便两者优先级相等，也出栈）

 然后在将此运算符进栈(如果出栈过程中遇到‘（’，停止出栈，将 此运算符进栈）；

3.如果是‘(',直接进栈；

4.如果是‘)',将栈中元素出栈，放入后缀表达式中，直到遇到‘('为止，并且‘('也要被出栈，但不可以放入后缀表达式中，直接丢弃；

代码实现：

俺是先用一个字符串数组接收输入的中缀表达式，但是不能直接对这个字符数组直接转后缀 表达式，如果直接转，会发生多个操作数连在一起

无法区分的情况，例如这样"931-4*+10 2/+"，9,3,1三个不同操作数连在一起成了一个操作数了， 为了避免这种状况，俺使用了一个指针数组，

将每个操作数从字符串数组中分离出来，并放在指针数组所指向的动态内存中，以此来将每个操作数区分开来，在将经过转换的表达式转换成

后缀表达式。

将字符串数组中的中缀表达式进行转换，防止操作数连在一起：

void checkInputConvert(char * infix, char ** opNum)
{
	int index1 = 0;
	int length = strlen(infix);
	for (int i = 0; i < length;)
	{
		char ch = infix[i];
		int index2 = 0;
		int charNum = 0;
		if (isNumber(ch))//判断是否是数字
		{
			
			charNum++;
			opNum[index1] = (char*)calloc(charNum + 1,sizeof(char));
			opNum[index1][index2++] = ch;
			while (isNumber(infix[i + charNum]))
			{
				charNum++;//统计单个操作数所包含的字符个数
				opNum[index1] = (char*)realloc(opNum[index1], sizeof(char)*(charNum + 1));
				opNum[index1][index2++] = infix[i + charNum - 1];
			}
 			i += charNum;
			opNum[index1++][index2] = '\0';//设置字符串结束符
			continue;//单个操作数已找完，跳出此次循环
		}

		if (isOperator(ch))//判断是否是操作符
		{
			opNum[index1] = (char*)calloc(2, sizeof(char));
			opNum[index1++][index2] = ch;
			i++;
			continue;
		}

		if (ch == '(' || ch == ')')
		{
			opNum[index1] = (char*)calloc(2, sizeof(char));
			opNum[index1++][index2] = ch;
			i++;
			continue;
		}
		printf("输入的数据有误，请重新输入！\n");
		exit(1);
	}

int isOperator(char ch)//判断是否是运算符
{
	char op[5] = "+-*/";
	for (int i = 0; i < 5; i++)
	{
		if (ch == op[i])
			return 1;
	}
	return 0;
}
int isNumber(char ch)
{
	if ((ch - '0') >= 0 && (ch - '0') <= 9)
		return 1;
	else
		return 0;
}

//比较优先级,ch未中缀表达式中的运算符，op为栈中的运算符或‘（’
//当op1的优先级小于op2的优先级时返回-1，大于时返回1,等于时返回0
int comparePrior(char op1, char op2)
{
	if (op1 == '+' || op1 == '-')
	{
		if (op2 == '*' || op2 == '/')
			return -1;
		if (op2 == '+' || op2 == '-')
			return 0;
	}

	if (op1 == '*' || op1 == '/')
	{
		if (op2 == '*' || op2 == '/')
			return 0;
		if (op2 == '+' || op2 == '-')
			return 1;
	}
	if (op2 == '(')
		return 1;
}

void infixToPrefix(char ** infix,char** prefix )//中缀表达式转后缀
{
	stack<char> LS;
	int index1 = 0;//指向infix中的下标
	int index2 = 0;//指向prefix中的下标
	while (infix[index1] != NULL)
	{
			char ch = infix[index1][0];
			if (ch == '(')//左括号入栈
			{
				LS.push(ch);
				index1++;//指向下一个字符串
				continue;
			}
			if (isNumber(ch))//数字输出到temp中
			{
				int length = strlen(infix[index1]);
				prefix[index2] = (char*)calloc(length + 1, sizeof(char));//测定该操作数所包含字符个数,并分配空间
				prefix[index2][length] = '\0';
				strcpy(prefix[index2++], infix[index1++]);//将字符串拷贝过来

				continue;
			}
			if (isOperator(ch))//判断是不是操作符
			{
				if (LS.empty())//栈空不比较，直接入栈
				{
					LS.push(ch);
					index1++;
				}
				else
				{
					if (comparePrior(ch, LS.top()) >= 0)//优先级高直接入栈
					{
						LS.push(ch);
					}
					else//优先级低需要将栈中优先级比ch高或等于的全部出栈
					{//如果有多个操作符出栈，将会把这些操作符存在同同一指针指向的字符数组中
						int num = 0;//记录要出栈的操作符的个数
						char temp[100] = { 0 };//用来暂存出栈的存操作符
						temp[num++] = LS.top();
						LS.pop();
						while (!LS.empty() && comparePrior(ch, LS.top()) <= 0)
						{
							temp[num++] = LS.top();
							LS.pop();
						}
						LS.push(ch);//所有比ch优先级大于等于的操作符已经出栈完成，将ch入栈
						prefix[index2] = (char *)calloc(++num, sizeof(char));
						prefix[index2][--num] = '\0';
						strcpy(prefix[index2++], temp);
					}
					index1++;
				}
				continue;
			}
			if (ch == ')')
			{
				int num = 0;//记录要出栈的操作符的个数
				char temp[100] = { 0 };//用来暂存出栈的存操作符
				while (LS.top() != '(')
				{
					temp[num++] = LS.top();
					LS.pop();
				}
				LS.pop();//将‘（’出栈
				prefix[index2] = (char *)calloc(++num, sizeof(char));
				prefix[index2][--num] = '\0';
				strcpy(prefix[index2++], temp);
				index1++;
				continue;
			}
		}
		if (!LS.empty())
		{
			int num = 0;//记录要出栈的操作符的个数
			char temp[100] = { 0 };//用来暂存出栈的存操作符
			while (!LS.empty())//此时中缀表达式已扫完，若栈中有剩余操作符，全部弹出，追加到prefix中
			{
				temp[num++] = LS.top();
				LS.pop();
			}
			prefix[index2] = (char *)calloc(++num, sizeof(char));
			strcpy(prefix[index2], temp);

		}
}

算法过程自己百度......

int calcPrefix(char ** prefix)//计算后缀表达式求值
{
	stack<double> LS;
	int index1 = 0;
	while (prefix[index1] != NULL)
	{
		int index2 = 0;
		char ch;
		if (isNumber(ch = prefix[index1][index2]))
		{
			double opNum = ch - '0';
			while ((ch = prefix[index1][++index2]) != '\0')
				opNum = opNum * 10 + (ch - '0');
			LS.push(opNum);
			index1++;
			continue;
		}

		flag:
		if (isOperator(ch = prefix[index1][index2]))
		{

			switch (ch)
			{
				case '+':
					{
						double opNum1 = LS.top();
						LS.pop();
						double opNum2 = LS.top();
						LS.pop();
						LS.push(opNum1 + opNum2);
						while ((ch = prefix[index1][++index2]) != '\0')
							goto flag;
						index1++;
						break;
					}
				case '-':
					{
						double opNum1 = LS.top();
						LS.pop();
						double opNum2 = LS.top();
						LS.pop();
						LS.push(opNum2 - opNum1);
						while ((ch = prefix[index1][++index2]) != '\0')
							goto flag;
						index1++;
						break;
					}
			case '*':
					{
						double opNum1 = LS.top();
						LS.pop();
						double opNum2 = LS.top();
						LS.pop();
						LS.push(opNum2 * opNum1);
						while ((ch = prefix[index1][++index2]) != '\0')
							goto flag;
						index1++;
						break;
					}
			case '/':
					{
						double opNum1 = LS.top();
						LS.pop();
						double opNum2 = LS.top();
						LS.pop();
						LS.push(opNum2 / opNum1);
						while ((ch = prefix[index1][++index2]) != '\0')
							goto flag;
						index1++;
						break;
					}
			}
			continue;
		}
	}
	return (LS.top());
}

#define  _CRT_SECURE_NO_WARNINGS
#include<stack>
#include<string.h>
#include<stdio.h>
using namespace::std;
int isOperator(char ch);//判断是否是运算符
int comparePrior(char op1,char op2);//比较优先级
int isNumber(char ch);
void infixToPrefix(char ** infix, char ** prefix);//中缀表达式转后缀
int calcPrefix(char ** prefix);//计算后缀表达式求值
void checkInputConvert(char * ch,char ** infix);//将输入的字符串转换为合理的中缀表达式
int main()
{
	
	while (1)
	{
		char ch[100] = "12+33-5*65/10+((343+34)*2)*3/4+34";
		char * infix[100] = { 0 };
		char * prefix[100] = { 0 };
		//printf("请输入要计算的表达式：\n");
		//scanf("%s", ch);
		printf("输入的中缀表达式为：%s\n", ch);
		checkInputConvert(ch, infix);
		char** p = infix;
		while (*p != NULL)
		{
			printf("%s", *p);
			p++;
		}
		infixToPrefix(infix, prefix);

		printf("\n%d\n",calcPrefix(prefix));
		system("pause");

	}
	return 0;
}

C语言计算后缀表达式，从控制台输入，以空格为分割输入，支持多位数和负数运算，支持加、减、乘、除、阶乘操作，支持表达式错误检测异常。

input：
3
1 -2 *
1 10 - 6 +
3 1 - ！
Output：
-2
-3
2

#include<stdio.h>
#include <ctype.h>
#include<string.h>
#include<stdlib.h>
#define MAX 1000
#define NUMMAX 100
typedef struct stack
{
	int data[MAX];
	int top;
}stack;

int func(int op);
void init(stack*);
int empty(stack*);
int full(stack*);
int pop(stack*);
void push(stack*, int);
int evaluate(char x, int op1, int op2);

int main()
{
	stack s;
	char x;
	int op1, op2, val, num;
	int flag = 0;
	init(&s);
	scanf_s("%d", &num);
	getchar();
	int result[1000];

	char str[1000][1024];
	for (int i = 0; i < num; ++i)
	{
		gets_s(str[i]);
	}
	
	for (int i = 0; i < num; ++i)
	{
		int j = 0;
		while(j < strlen(str[i]))
		{
			x = str[i][j];
			int digitNum = 0 , sign = 0;
			char* digitnum = (char*)malloc(1024*sizeof(char));
			//char* digitnum = new char(100 * sizeof(char));
			if (isdigit(x))
			{
				while (str[i][j] != ' ' && str[i][j] != '\0')
				{
					digitnum[sign] = str[i][j];
					j++;
					sign++;
				}
				digitNum = atoi(digitnum);
				if (flag == 0) push(&s, digitNum);
				if (flag == -1)
				{
					push(&s, digitNum * flag);
					flag = 0;
				}
			}
			if (x == ' ')
			{
				j++;
				continue;
			}
			if (x == '-' && str[i][j+1] != ' ')
			{
				flag = -1;
				j++;
				continue;
			}
			if(x == '+' || x == '-' || x == '*' || x == '/' || x == '!')
			{
				if (x == '!')
				{
					op2 = pop(&s);
					op1 = 1;
				}
				else
				{
					op2 = pop(&s);
					op1 = pop(&s);
				}
				
				val = evaluate(x, op1, op2);
				if (val == -9999 || val == -1111)
				{
					push(&s, val);
					break;
				}
				else {
					push(&s, val);
				}
			}
			j++;
			free(digitnum);
		}
		val =  pop(&s);
		result[i] = val;
		
		init(&s);
	}
	for (int j = 0; j < num; ++j)
	{
		if(result[j] == -9999)
		{
			printf("division by zero\n");

		}
		else if (result[j] == -1111)
		{
			printf("factorial of an negative number\n");
		}
		else
		{
			printf("%d\n", result[j]);
		}

	}
	return 0;
}

int evaluate(char x, int op1, int op2)
{
	if (x == '+')
		return(op1 + op2);
	if (x == '-')
		return(op1 - op2);
	if (x == '*')
		return(op1 * op2);
	if (x == '/')
	{
		if (op2 == 0)
		{
			return -9999;
		}
		else
		{
			return(op1 / op2);
		}
	}
			
	if (x == '!')
	{
		if ( op2 >= 0)
		{
			return func(op2);
		}
		if(op2 < 0)
		{
			return -1111;
		}
	}
		
}

int func(int n)
{
	int sum = 1;
	for (int i = 1; i <= n; ++i)
	{
		sum = sum * i;
	}
	
	return sum;
}

void init(stack* s)
{
	s->top = -1;
}

int empty(stack* s)
{
	if (s->top == -1)
		return(1);

	return(0);
}

int full(stack* s)
{
	if (s->top == MAX - 1)
		return(1);

	return(0);
}

void push(stack* s, int x)
{
	s->top = s->top + 1;
	s->data[s->top] = x;
}

int pop(stack* s)
{
	int x;
	if (s->top == -1)
	{
		return 8888;
	}
	else
	{
		x = s->data[s->top];
		s->top = s->top - 1;
	}
	

	return(x);
}

如何实现栈

如何利用栈将中缀表达式转换为后缀表达式

题目

我们平常使用的计算表达式都是中缀表达式，而输入计算机后会转换为后缀表达式，即计算机只能计算后缀表达式，那么如何计算机是如何计算后缀表达式的值的呢？

算法

1）从左到右扫描后缀表达式字符串
2）初始化一个空栈
3）如果扫描到数字，那么就直接入栈
4）如果被扫描的字符是一个二元运算符，那么就连续出栈两次，获得两个字符，元素出栈后，应用运算符进行计算，并将结果压栈
5）重复3）和4）的操作，直至扫描完字符串
6）扫描完所有字符串之后，栈中只剩一个元素，该元素就是最终结果，将其出栈并返回。

Java版本实现

	
	//计算后缀表达式算法
    static Double calculator(String curString) {
        LLStack<Double> stack = new LLStack<>();
        for(int i = 0; i < curString.length(); i++) {
            String t = curString.substring(i , i + 1 );
            if(t.charAt(0) >= '0' && t.charAt(0) <= '9' ) {
                //数字直接入栈
                stack.push(Double.parseDouble(t));
            }else {
                double a , b = 0;
                a =(Double) stack.pop();
                b =(Double) stack.pop();
                switch(t){
                    case "*" : stack.push(b * a);System.out.println(t+":" + b * a);break;
                    case "/" : stack.push(b / a);System.out.println(t+":" + b / a);break;
                    case "+" : stack.push(b + a);System.out.println(t+":" + (double)(b + a));break;
                    case "-" : stack.push(b - a);break;
                    case "%" : stack.push(b % a);break;
                }
            }
        }
        return stack.pop() ;
    }

栈的实现

class LLNode<T>{
    private T data;
    private LLNode next = null;

    public LLNode(T d){
        data = d;
    }
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LLNode getNext() {
        return next;
    }
    public void setNext(LLNode next) {
        this.next = next;
    }


}
public class LLStack<T> {
    private LLNode<T>  head;

    boolean isEmpty() {
        return head == null;
    }

    int size() {
        int count = 1;
        LLNode cur = head;
        if(isEmpty())  return 0;
        while(cur.getNext() !=null ) {
            cur = cur.getNext();
            count++;
        }
        return count;
    }

    T top() {
        if(isEmpty())
            new Exception("栈空");
        return head.getData();
    }

    void push(T d) {
        if(isEmpty()) {
            head =new LLNode(d);
        }else {
            LLNode node = new LLNode(d);
            node.setNext(head);
            head = node;
        }
    }

    T pop() {
        if(isEmpty())
            new Exception("栈空");
        LLNode<T> del = head;
        head = head.getNext();
        return del.getData();
    }
    void display() {
        if(isEmpty()) {
            System.out.println("栈空");
        }else {
            LLNode cur = head;
            System.out.print("栈内元素：");
            while(cur != null) {
                System.out.print(cur.getData() + "->");
                cur = cur.getNext();
            }
            System.out.println();
        }
    }

    void deleteStack() {
        head  = null;
    }



    public static void main(String[] args) {
        LLStack<Character> ls = new LLStack<>();
        ls.push('2');
        ls.push('3');
        System.out.println("栈顶元素：" + ls.top());
        ls.display();
        System.out.println("移除栈顶元素：" + ls.pop());
        ls.push('5');
        System.out.println("删除整个栈");
        ls.deleteStack();
        ls.display();

    }

}

完整测试代码

import java.util.Scanner;

public class StackApplication {
    //括号匹配算法
    static boolean isMatch(String curString) {
        LLStack<Character> stack = new LLStack<>();
        //字符处理
        for(int i = 0; i < curString.length(); i++) {
            char ch = curString.charAt(i);
            switch(ch) {
                case '(' :
                    stack.push(ch);
                    break;
                case '[' :
                    stack.push(ch);
                    break;
                case '{' :
                    stack.push(ch);
                    break;
                case ')' :
                    if(stack.isEmpty() || stack.top().equals('c')) {
                        System.out.println("括号匹配失败");
                        return false;
                    }else {
                        stack.pop();
                    }
                    break;
                case ']' :
                    if(stack.isEmpty() || stack.top().equals('[') ) {
                        System.out.println("括号匹配失败");
                        return false;
                    }else {
                        stack.pop();
                    }
                    break;
                case '}' :
                    if(stack.isEmpty() || stack.top().equals('{') ) {
                        System.out.println("括号匹配失败");
                        return false;
                    }else {
                        stack.pop();
                    }
                    break;
            }
        }
        //字符处理后栈非空
        if(!stack.isEmpty()) {
            System.out.println("括号匹配失败");
            return false;
        }
        //System.out.println("括号匹配成功");
        return true;
    }
    //算术符号优先级算法
    static boolean isPriority(char top, char t) {
        /*if(a == '(' || a == '[' || a == '{') return true;
        if(b == '(' || b == '[' || b == '{' ) return true;

        if(b == '*' || b == '/' || b == '%')
            return false;
        else if(a == '*' || a == '/' || a == '%')
            return true;
        else if(b == '+' || b == '-' )
            return false;
        else return true;
*/
        if((t == '+' || t == '-') && (top == '*' || top == '/'))
            return true;
        return false;

    }

    static boolean isNumber(char t){
        //这里为了测试一下字母，所以把字母也加进来了
        if (t >= '0' && t <= '9' || t >= 'a' && t <= 'z' || t >= 'A' && t <= 'Z' )
            return  true;
        return false;
    }
    //中缀转后缀算法
    static String MinddleTurnToBack(String curString) {
        LLStack<Character> stack = new LLStack<>();
        String result = "" ;
        System.out.print("中缀表达式转换为后缀表达式：");
        for(int i = 0; i < curString.length(); i++) {
            char t = curString.charAt(i);
            if(isNumber(t)) {
                //数字直接输出
                System.out.print(t);
                result = result + t;
            }else if((t == ')' || t == ']' || t == '}')) {
                //当栈顶不是‘（’时，出栈并输出
                while(!stack.isEmpty() && stack.top() != '(' && stack.top() != '[' && stack.top()!= '{'){
                    result += stack.top();
                    System.out.print((char)stack.pop());

                }
                //直到栈顶是‘（’
                if (!stack.isEmpty())
                    stack.pop();

            }else {//操作符或‘(’
                //当栈非空且t的优先级不大于栈顶元素时，出栈并输出然后t入栈
                while(!stack.isEmpty() && isPriority((char)stack.top(), t)) {
                    result += stack.top();
                    System.out.print((char)stack.pop());
                }
                stack.push(t);
            }
        }
        while(!stack.isEmpty()) {
            result += stack.top();
            System.out.print((char)stack.pop());
        }
        System.out.println();
        return result;
    }
    //计算后缀表达式算法
    static Double calculator(String curString) {
        LLStack<Double> stack = new LLStack<>();
        for(int i = 0; i < curString.length(); i++) {
            String t = curString.substring(i , i + 1 );
            if(t.charAt(0) >= '0' && t.charAt(0) <= '9' ) {
                //数字直接入栈
                stack.push(Double.parseDouble(t));
            }else {
                double a , b = 0;
                a =(Double) stack.pop();
                b =(Double) stack.pop();
                switch(t){
                    case "*" : stack.push(b * a);System.out.println(t+":" + b * a);break;
                    case "/" : stack.push(b / a);System.out.println(t+":" + b / a);break;
                    case "+" : stack.push(b + a);System.out.println(t+":" + (double)(b + a));break;
                    case "-" : stack.push(b - a);break;
                    case "%" : stack.push(b % a);break;
                }
            }
        }
        return stack.pop() ;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String curString = null;
        while(true) {
            System.out.print("请输入中缀表达式：");
            curString = scanner.next();
            if(isMatch(curString))
                System.out.println("计算出后缀表达式的结果为：" + calculator(MinddleTurnToBack(curString)));
            //MinddleTurnToBack(curString);
            System.out.println();
        }
    }
}